Codeforces Round 966 (Div. 3) H（线段树上二分）

题意

思路

1、定义$F(x)$代表了正整数$x$所代表的集合负载，例如对于集合$3,4,6,11$而言，$F(5)=1，F(7)=4$.
2、可以发现：对于集合中相邻两个数之间的数字，其$F(x)$是递减的,例如上述例子中$F(7)=4,F(8)=3,F(9)=2,F(10)=1$
3、对于一个询问$?$而言，我们需要找到的是$x$的最小值，满足 $k\le F(x)$.
4、由于观察2，对于集合中相邻两个数之间的数字而言，若最左侧的$k>F(x)$,那么这个区间内所有的数都无法满足，因此我们只需要记录所有区间的最左侧数即可。
5、为了表示集合中最小的数左侧的$F(x)$跟最大的数右侧的$F(x)$,我们可以默认在集合中添加$0$跟一个$inf$.
6、考虑添加一个数，所有的$F(x)$会如何变化：假设集合中小于$x$的最大元素为$l$，大于$x$的最小元素为$r$.那么$F(l+1)=x-l-1,F(x+1)=r-x-1$.其余的由于观察2，我们都不需要统计。删除一个数也是同理。
7、对于查询而言，我们想到了一个母题：一个数组中第一个大于等于$x$的下标。我们的思路是分治，若左侧区间的最大值大于等于$x$，那么就对左侧区间继续查询，否则就去找右侧区间。暴力的遍历整个区间求最值的时间复杂度是$O(nlogn)$的，我们考虑用线段树来维护区间最值，这样时间复杂度就变成了$O(lognlogn)$，可以完成本题。

代码

// Problem: H. Ksyusha and the Loaded Set
// Contest: Codeforces - Codeforces Round 966 (Div. 3)
// URL: https://codeforces.com/contest/2000/problem/H
// Memory Limit: 512 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL N = 2e06+7;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
template<class Info>
struct SegmentTree {int n;std::vector<Info> info;SegmentTree() : n(0) {}SegmentTree(int n_, Info v_ = Info()) {init(n_, v_);}template<class T>SegmentTree(std::vector<T> init_) {init(init_);}template<class T>void init(std::vector<T> init_) {n = init_.size();info.assign(4 << std::__lg(n), Info());std::function<void(int, int, int)> build = [&](int p, int l, int r) {if (r - l == 1) {info[p] = init_[l];return;}int m = (l + r) / 2;build(2 * p, l, m);build(2 * p + 1, m, r);pull(p);};build(1, 0, n);}void pull(int p) {info[p] = info[2 * p] + info[2 * p + 1];}void modify(int p, int l, int r, int x, const Info &v) {if (r - l == 1) {info[p] = v;return;}int m = (l + r) / 2;if (x < m) {modify(2 * p, l, m, x, v);} else {modify(2 * p + 1, m, r, x, v);}pull(p);}void modify(int p, const Info &v) {modify(1, 0, n, p, v);}Info rangeQuery(int p, int l, int r, int x, int y) {if (l >= y || r <= x) {return Info();}if (l >= x && r <= y) {return info[p];}int m = (l + r) / 2;return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);}Info rangeQuery(int l, int r) {return rangeQuery(1, 0, n, l, r);}template<class F>int findFirst(int p, int l, int r, int x, int y, F pred) {if (l >= y || r <= x || !pred(info[p])) {return -1;}if (r - l == 1) {return l;}int m = (l + r) / 2;int res = findFirst(2 * p, l, m, x, y, pred);if (res == -1) {res = findFirst(2 * p + 1, m, r, x, y, pred);}return res;}template<class F>int findFirst(int l, int r, F pred) {return findFirst(1, 0, n, l, r, pred);}template<class F>int findLast(int p, int l, int r, int x, int y, F pred) {if (l >= y || r <= x || !pred(info[p])) {return -1;}if (r - l == 1) {return l;}int m = (l + r) / 2;int res = findLast(2 * p + 1, m, r, x, y, pred);if (res == -1) {res = findLast(2 * p, l, m, x, y, pred);}return res;}template<class F>int findLast(int l, int r, F pred) {return findLast(1, 0, n, l, r, pred);}
};
struct Info {int max = 0;
};
Info operator + (Info a, Info b) {return {max(a.max , b.max)};
}
vector<Info>v(N , {0});
SegmentTree<Info>seg(v);
void solve() 
{int n;cin >> n;set<int>st;st.insert(0);st.insert(N * 2);for(int i = 0 ; i < n ; i ++){int x;cin >> x;st.insert(x);}int pre = 0;for(auto it : st){if(it == 0){pre = 0;}else{seg.modify(pre + 1 , {it - pre - 1});pre = it;}}int m;cin >> m;auto del =[&] (int x){st.erase(x);auto it = st.upper_bound(x);seg.modify(x + 1 , {});int r = *it;it--;int l = *it;seg.modify(l + 1 , {r - l - 1});};auto add =[&](int x){auto it = st.upper_bound(x);int r = *it;it--;int l = *it;seg.modify(l + 1 , {x - l - 1});seg.modify(x + 1 , {r - x - 1});st.insert(x);		};for(int i = 0 ; i < m ; i++){char op;cin >> op;if(op == '-'){int x;cin >> x;del(x);}	else if(op == '+'){int x;cin >> x;add(x);}else{int k;cin >> k;int l = 0 , r = N;while(l < r){int mid = (l + r + 1) >> 1;Info tl = seg.rangeQuery(l , mid);Info tr = seg.rangeQuery(mid , r);if(tl.max >= k){r = mid - 1;}else{l = mid;}}cout << l << " ";}}cout << endl;for(auto it : st){seg.modify(it + 1 , {});}
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}