牛客round95D

原题链接：D-小红的区间修改（一）_牛客周赛 Round 95

题目背景：

        初始拥有一个长度10^100元素全为0的数组，进行q查询，每次查询如果区间内的元素都为0就将区间变为首项为 1、公差为 1 的等差数列；否则不进行任何操作。输出每次操作后数组不同元素的个数。

数据范围：

        1 <= q <= 3e5，1 <= l，r <= 3e5。

解法1（赛时想到的暴力解法）：

思路：

       看到区间修改动态更新数据范围还是3e5就不难想到使用线段树。

        每次查询区间判断区间和是否为0即可，如果为0且当前区间大于之前的所有区间就更新答案并输出，否者输出历史最大答案。

ac代码： 

#include <bits/stdc++.h>#define ioscc ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define me(a, x) memset(a, x, sizeof a)
#define all(a) a.begin(), a.end()
#define sz(a) ((int)(a).size())
#define pb(a) push_back(a)
using namespace std;typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<bool> vb;const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAX = (1ll << 31) - 1;
const int MIN = 1 << 31;
const int MOD = 1e9 + 7;
const int N = 3e5 + 10;template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cout << a[i] << ' ';return os;
}template <class T>
istream &operator>>(istream &in, vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cin >> a[i];return in;
}/* ----------------- 有乘就强转，前缀和开ll ----------------- */struct Node
{int l, r;ll sum;ll add;
} tr[N * 4];void pushup(int u)
{tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}void pushdown(int u)
{if (tr[u].add){tr[u << 1].sum += tr[u].add * (tr[u << 1].r - tr[u << 1].l + 1);tr[u << 1 | 1].sum += tr[u].add * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1);tr[u << 1].add += tr[u].add;tr[u << 1 | 1].add += tr[u].add;tr[u].add = 0;}
}void build(int u, int l, int r)
{tr[u] = {l, r, 0, 0};if (l == r)return;int mid = (l + r) >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}ll query(int u, int l, int r)
{if (tr[u].l >= l && tr[u].r <= r)return tr[u].sum;pushdown(u);int mid = (tr[u].l + tr[u].r) >> 1;ll sum = 0;if (l <= mid)sum = query(u << 1, l, r);if (r > mid)sum += query(u << 1 | 1, l, r);return sum;
}void update(int u, int l, int r, int v)
{if (tr[u].l >= l && tr[u].r <= r){tr[u].sum += (ll)(tr[u].r - tr[u].l + 1) * v;tr[u].add += v;return;}int mid = (tr[u].l + tr[u].r) >> 1;pushdown(u);if (l <= mid)update(u << 1, l, r, v);if (r > mid)update(u << 1 | 1, l, r, v);pushup(u);
}void solve()
{build(1, 1, N);int sum = 0; // 元素个数int q;cin >> q;while (q--){int l, r;cin >> l >> r;int len = r - l + 1;int t = query(1, l, r);if (t){cout << sum + 1 << endl;continue;}update(1, l, r, 1);if (len > sum)sum = len;cout << sum + 1 << endl;}
}int main()
{ioscc;solve();return 0;
}

解法2（官方解法）：

思路：

        将先前处理过的区间内所有元素的下标存到set里面，每次使用给出的 l 二分找最大的边界（没有元素就为尾迭代器），如果找到的边界大于 r 就说明可以区间全为 0 ，即可放置，否者不能放置；每次将区间内的元素都插入到 set 中，每个元素最多插入 1 次。

ac代码：

#include <bits/stdc++.h>#define ioscc ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define me(a, x) memset(a, x, sizeof a)
#define all(a) a.begin(), a.end()
#define sz(a) ((int)(a).size())
#define pb(a) push_back(a)
using namespace std;typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<bool> vb;const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAX = (1ll << 31) - 1;
const int MIN = 1 << 31;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cout << a[i] << ' ';return os;
}template <class T>
istream &operator>>(istream &in, vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cin >> a[i];return in;
}/* ----------------- 有乘就强转，前缀和开ll ----------------- */void solve()
{int q;cin >> q;int maxx = 0;set<int> s;while (q--){int l, r;cin >> l >> r;auto it = s.lower_bound(l);if (it == s.end() || *it > r){maxx = max(maxx, r - l + 1);for (int i = l; i <= r; ++i)s.emplace(i);}cout << maxx + 1 << endl;}
}int main()
{ioscc;solve();return 0;
}

解法3（大佬解法）：

思路：

        与解法2类似，不过多赘述。

ac代码：

#include <bits/stdc++.h>#define ioscc ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define me(a, x) memset(a, x, sizeof a)
#define all(a) a.begin(), a.end()
#define sz(a) ((int)(a).size())
#define pb(a) push_back(a)
using namespace std;typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<bool> vb;const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAX = (1ll << 31) - 1;
const int MIN = 1 << 31;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cout << a[i] << ' ';return os;
}template <class T>
istream &operator>>(istream &in, vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cin >> a[i];return in;
}/* ----------------- 有乘就强转，前缀和开ll ----------------- */void solve()
{int q;cin >> q;map<int, int> mp;set<int> s;int mx = 0;while (q--){int l, r;cin >> l >> r;if (s.empty()){s.insert(r);mp[r] = l;mx = r - l + 1 + 1;cout << mx << endl;}else{auto p = s.lower_bound(l);int rr = *s.lower_bound(l);int ll = mp[rr];if (ll > r || rr < l || p == s.end()){s.insert(r);mp[r] = l;mx = max(mx, r - l + 1 + 1);cout << mx << endl;}else{cout << mx << endl;}}}
}int main()
{ioscc;solve();return 0;
}