题目描述
难度分:2200
输入T(≤104)表示T组数据。所有数据的n之和≤2×105,m之和≤2×105。
每组数据输入n(1≤n≤2×105)和长为n的严格递增数组a(1≤a[i]≤2×106)。a表示n个数的集合S。
然后输入m(1≤m≤2×105)和m个询问,格式如下:
+ x
:往集合S中添加元素x(1≤x≤2×106),保证x不在S中。
- x
:从集合S中移除元素x(1≤x≤2×106),保证x在S中。
? k
:输出最小的正整数d,满足[d,d+k−1]中的整数都不在S中。(1≤k≤2×106)
输入样例
3
5
1 2 5 905 2000000
15
- 2
? 2
? 1
- 1
? 1
+ 4
+ 2
? 2
+ 6
- 4
+ 7
? 2
? 3
? 4
? 2000000
5
3 4 5 6 8
9
? 5
- 5
? 5
+ 1
? 2
- 6
- 8
+ 6
? 5
5
6 7 8 9 10
10
? 5
- 6
? 4
- 10
+ 5
- 8
+ 3
+ 2
- 3
+ 10
输出样例
2 2 1 6 3 8 8 2000001
9 9 9 7
1 1
算法
有序表模拟
准备一个存二元组(l,r)的有序集合intervals,其中的每个二元组表示集合S中不存在的一段连续区间,且满足1≤l≤r。再准备一个映射表len2pos,表示“长度→这个长度的连续区间的左端点集合(有序集合)”。
对于+
和-
操作,其实就是区间分裂与合并,在这个过程中维护intervals和len2pos两个数据结构。
- 如果是
+
操作,就是分裂操作,二分找到包含x的区间,把原区间从intervals中删掉,将分裂后得到的非空区间插入。 - 如果是
-
操作,就是合并操作,二分找到x左右两边的区间(不一定两个邻居都存在),看能不能将邻居合并起来。 - 如果是
?
操作,二分找到len2pos中第一个长度≥k的key,然后从它开始遍历后面的区间,维护左端点的最小值。
其实乍一眼看感觉?
的遍历操作是会导致超时的,但是我们注意到最差情况下,所有intervals中区间的长度都不相同,但是它们加起来是O(n)级别的长度,所以最多也就O(√n)个key,这个遍历的时间复杂度为O(√n),可以过。
复杂度分析
时间复杂度
遍历i∈[1,n],对于每个i会有有序表的插入操作,所以初始化len2pos和intervals两个数据结构的时间复杂度为O(nlog2n)。接下来O(m)个操作,瓶颈在于?
操作,它需要先进行二分查找再遍历,时间复杂度为O(log2n+√n),所以时间复杂度为O(m(log2n+√n))。整个算法的时间复杂度为O(nlog2n+m(log2n+√n))。
空间复杂度
空间消耗就在于两个数据结构,len2pos中需要存O(n)级别的端点坐标,intervals中需要存O(n)级别的区间个数。因此整个算法的额外空间复杂度为O(n)。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 200010, INF = 0x3f3f3f3f;
int t, n, m, a[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> t;
while(t--) {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
map<int, set<int>> len2pos;
set<PII> intervals;
if(a[1] > 1) {
intervals.insert({1, a[1] - 1});
int len = a[1] - 1;
len2pos[len].insert(1);
}
for(int i = 2; i <= n; i++) {
if(a[i - 1] + 1 < a[i]) {
// a[i-1]和a[i]之间有数
intervals.insert({a[i - 1] + 1, a[i] - 1});
int len = a[i] - 1 - a[i - 1];
len2pos[len].insert(a[i - 1] + 1);
}
}
intervals.insert({a[n] + 1, INF});
len2pos[INF - a[n]].insert(a[n] + 1);
cin >> m;
for(int i = 1; i <= m; i++) {
char op;
int x;
cin >> op >> x;
if(op == '+') {
auto it = intervals.upper_bound({x, INF});
--it;
int l = it->first, r = it->second;
intervals.erase({l, r});
int len = r - l + 1;
len2pos[len].erase(l);
if(len2pos[len].empty()) len2pos.erase(len);
if(l <= x - 1) {
len = x - l;
intervals.insert({l, x - 1});
len2pos[len].insert(l);
}
if(x + 1 <= r) {
len = r - x;
intervals.insert({x + 1, r});
len2pos[len].insert(x + 1);
}
}else if(op == '-') {
auto itr = intervals.upper_bound({x, INF});
auto itl = prev(itr);
int l1 = itl->first, r1 = itl->second, l2 = itr->first, r2 = itr->second;
if(itr != intervals.begin()) {
if(r1 + 1 == x && x + 1 == l2) {
int len = r1 - l1 + 1;
len2pos[len].erase(l1);
if(len2pos[len].empty()) len2pos.erase(len);
intervals.erase({l1, r1});
len = r2 - l2 + 1;
len2pos[len].erase(l2);
if(len2pos[len].empty()) len2pos.erase(len);
intervals.erase({l2, r2});
len = r2 - l1 + 1;
len2pos[len].insert(l1);
intervals.insert({l1, r2});
}else if(x + 1 == l2) {
int len = r2 - l2 + 1;
len2pos[len].erase(l2);
if(len2pos[len].empty()) len2pos.erase(len);
intervals.erase({l2, r2});
len = r2 - x + 1;
len2pos[len].insert(x);
intervals.insert({x, r2});
}else if(r1 + 1 == x) {
int len = r1 - l1 + 1;
len2pos[len].erase(l1);
if(len2pos[len].empty()) len2pos.erase(len);
intervals.erase({l1, r1});
len = x - l1 + 1;
len2pos[len].insert(l1);
intervals.insert({l1, x});
}else {
intervals.insert({x, x});
len2pos[1].insert(x);
}
}else {
if(x + 1 == l2) {
int len = r2 - l2 + 1;
len2pos[len].erase(l2);
if(len2pos[len].empty()) len2pos.erase(len);
intervals.erase({l2, r2});
len = r2 - x + 1;
len2pos[len].insert(x);
intervals.insert({x, r2});
}else {
intervals.insert({x, x});
len2pos[1].insert(x);
}
}
}else {
int ans = INF;
auto it = len2pos.lower_bound(x);
while(it != len2pos.end()) {
ans = min(ans, *it->second.begin());
++it;
}
cout << ans << ' ';
}
}
cout << '\n';
}
return 0;
}