题目描述

难度分:$2200$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$，$m$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的严格递增数组$a(1 \leq a[i] \leq 2 \times 10^6)$。$a$表示$n$个数的集合$S$。

然后输入$m(1 \leq m \leq 2 \times 10^5)$和$m$个询问，格式如下：

+ x：往集合$S$中添加元素$x(1 \leq x \leq 2 \times 10^6)$，保证$x$不在$S$中。
- x：从集合$S$中移除元素$x(1 \leq x \leq 2 \times 10^6)$，保证$x$在$S$中。
? k：输出最小的正整数$d$，满足$[d,d+k-1]$中的整数都不在$S$中。$(1 \leq k \leq 2 \times 10^6)$

输入样例

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 \leq l \leq r$。再准备一个映射表$len2pos$，表示“长度$\rightarrow$这个长度的连续区间的左端点集合（有序集合）”。

对于+和-操作，其实就是区间分裂与合并，在这个过程中维护$intervals$和$len2pos$两个数据结构。

1. 如果是+操作，就是分裂操作，二分找到包含$x$的区间，把原区间从$intervals$中删掉，将分裂后得到的非空区间插入。
2. 如果是-操作，就是合并操作，二分找到$x$左右两边的区间（不一定两个邻居都存在），看能不能将邻居合并起来。
3. 如果是?操作，二分找到$len2pos$中第一个长度$\geq k$的$key$，然后从它开始遍历后面的区间，维护左端点的最小值。

其实乍一眼看感觉?的遍历操作是会导致超时的，但是我们注意到最差情况下，所有$intervals$中区间的长度都不相同，但是它们加起来是$O(n)$级别的长度，所以最多也就$O(\sqrt{n})$个$key$，这个遍历的时间复杂度为$O(\sqrt{n})$，可以过。

复杂度分析

时间复杂度

遍历$i \in [1,n]$，对于每个$i$会有有序表的插入操作，所以初始化$len2pos$和$intervals$两个数据结构的时间复杂度为$O(nlog_2n)$。接下来$O(m)$个操作，瓶颈在于?操作，它需要先进行二分查找再遍历，时间复杂度为$O(log_2n+\sqrt{n})$，所以时间复杂度为$O(m(log_2n+\sqrt{n}))$。整个算法的时间复杂度为$O(nlog_2n+m(log_2n+\sqrt{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;
}