原題鏈接：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;
}