Codeforces Round 904 (Div. 2) C

C. Medium Design

思路：我们设最大值所在的下标为$x$,最小值所在的下标为$y$,那么我们考虑一段区间对于答案的贡献：
若一段区间覆盖了$x$，但没有覆盖$y$,那么这段区间需要选择

若一段区间覆盖了$y$，但没有覆盖$x$，那么这段区间不选择

若一段区间覆盖了$x$,并且覆盖了$y$，那么这段区间选或者不选都可以

若一段区间对于$x$，$y$都未曾覆盖，那么这段区间同样选或是不选都可以

所以我们发现，真正需要进行判断的只有前两种情况，那么我们考虑极端情况，我们是否可以令每个位置为最大值（即把包含该点的线段全部选上），然后求出其对应的最小值？，最终的答案为所有差值中的最大值。

因为要进行多次区间修改和查询，所以使用线段树进行维护，又因为实际上只有 1e5 个点，所以我们可以通过对每个点去遍历得到答案，具体使用优先队列去进行维护，我们使用两个优先队列，第一个优先队列维护增加的线段，第二个优先队列维护应该减去的线段，所以第二个优先队列按照右端点进行排序，当我们把这条线段加入答案后，将其放入第二个优先队列中，若第二个优先队列中存在不合法的线段，即右端点小于当前点$i$，则将该线段删去即可。

#include <bits/stdc++.h>using namespace std;
const int N = 2e6 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 998244353;
const int maxv = 4e6 + 5;
// #define endl "\n"struct node
{ll l, r, add, maxv, minv;#define l(x) tr[x].l#define r(x) tr[x].r#define sum(x) tr[x].sum#define add(x) tr[x].add#define maxv(x) tr[x].maxv#define minv(x) tr[x].minv
} tr[N];void update(int p)
{maxv(p) = max(maxv(p * 2), maxv(p * 2 + 1));minv(p) = min(minv(p * 2), minv(p * 2 + 1));
}void build(int p, int l, int r)
{if (l == r){tr[p] = {l, r, 0, 0, 0};return;}l(p) = l, r(p) = r, maxv(p) = 0, minv(p) = 0, add(p) = 0;int mid = (l + r) / 2;build(p * 2, l, mid);build(p * 2 + 1, mid + 1, r);update(p);
}void up(int p, int tag)
{add(p) += tag;maxv(p) += tag;minv(p) += tag;
}void pushdown(int p)
{if (add(p)){up(p * 2, add(p)), up(p * 2 + 1, add(p));add(p) = 0;}
}void modify(int p, int l, int r, int tag)
{if (l <= l(p) && r(p) <= r){up(p, tag);return;}pushdown(p);int mid = (l(p) + r(p)) / 2;if (l <= mid)modify(p * 2, l, r, tag);if (r > mid)modify(p * 2 + 1, l, r, tag);update(p);
}ll querymax(int p, int l, int r)
{if (l <= l(p) && r(p) <= r){// cout<<l<<" "<<r<<" "<<sum(p)<<endl;return maxv(p);}pushdown(p);int mid = (l(p) + r(p)) / 2;ll res = 0;if (l <= mid)res = querymax(p * 2, l, r);if (r > mid)res = max(res, querymax(p * 2 + 1, l, r));return res;
}ll querymin(int p, int l, int r)
{if (l <= l(p) && r(p) <= r){// cout<<l<<" "<<r<<" "<<sum(p)<<endl;return minv(p);}pushdown(p);int mid = (l(p) + r(p)) / 2;ll res = 2e9;if (l <= mid)res = querymin(p * 2, l, r);if (r > mid)res = min(res, querymin(p * 2 + 1, l, r));return res;
}int cal(int l, int r)
{return querymax(1, l, r) - querymin(1, l, r);
}
void solve()
{int n, m;cin >> n >> m;vector<pll> se(n);vector<int> p;for (int i = 0; i < n; i++){int x, y;cin >> x >> y;se[i] = {x, y};p.push_back(x), p.push_back(y);}p.push_back(1);p.push_back(m);sort(p.begin(), p.end());p.erase(unique(p.begin(), p.end()), p.end());for (int i = 0; i < n; i++){auto [l, r] = se[i];l = lower_bound(p.begin(), p.end(), l) - p.begin();r = lower_bound(p.begin(), p.end(), r) - p.begin();se[i] = {l + 1, r + 1};}sort(se.begin(), se.end(), [](pll x, pll y){ return x.second < y.second; });int st = lower_bound(p.begin(), p.end(), 1) - p.begin();st++;int ed = lower_bound(p.begin(), p.end(), m) - p.begin();ed++;build(1, st, ed);priority_queue<pll, vector<pll>, greater<pll>> x, y;for (auto [l, r] : se)x.push({l, r});int ans = 0;for (int i = 0; i < p.size(); i++){// auto [nx,ny]=x.top();int tar = i+1;while (x.size() && x.top().first <= tar && x.top().second >= tar){auto [nl, nr] = x.top();x.pop();y.push({nr, nl});modify(1, nl, nr, 1);}while (y.size() && y.top().first < tar){auto [nl, nr] = y.top();y.pop();modify(1, nr, nl, -1);}ans = max(ans, cal(st, ed));}cout << ans << endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t = 1;cin >> t;while (t--){solve();}system("pause");return 0;
}