H. Ksyusha and the Loaded Set
Ksyusha decided to start a game development company. To stand out among competitors and achieve success, she decided to write her own game engine. The engine must support a set initially consisting of $n$ distinct integers $a_1, a_2, \ldots, a_n$.
The set will undergo $m$ operations sequentially. The operations can be of the following types:
- Insert element $x$ into the set;
- Remove element $x$ from the set;
- Report the $k$-load of the set.
The $k$-load of the set is defined as the minimum positive integer $d$ such that the integers $d, d + 1, \ldots, d + (k - 1)$ do not appear in this set. For example, the $3$-load of the set $\{3, 4, 6, 11\}$ is $7$, since the integers $7, 8, 9$ are absent from the set, and no smaller value fits.
Ksyusha is busy with management tasks, so you will have to write the engine. Implement efficient support for the described operations.
Input
The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The following lines describe the test cases.
The first line contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the initial size of the set.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_1 < a_2 < \ldots < a_n \le 2 \cdot 10^6$) — the initial state of the set.
The third line contains an integer $m$ ($1 \le m \le 2 \cdot 10^5$) — the number of operations.
The next $m$ lines contain the operations. The operations are given in the following format:
- + $x$ ($1 \le x \le 2 \cdot 10^6$) — insert element $x$ into the set (it is guaranteed that $x$ is not in the set);
- - $x$ ($1 \le x \le 2 \cdot 10^6$) — remove element $x$ from the set (it is guaranteed that $x$ is in the set);
- ? $k$ ($1 \le k \le 2 \cdot 10^6$) — output the value of the $k$-load of the set.
It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$, and the same holds for $m$.
Output
For each test case, output the answers to the operations of type "?".
Example
Input
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
+ 10Output
2 2 1 6 3 8 8 2000001
9 9 9 7
1 1
解题思路
和这题 P2894 [USACO08FEB] Hotel G 几乎一样。
把插入 $x$ 看成在下标 $x$ 处出置为 $1$，移除 $x$ 就置为 $0$，询问就相当于在 $1 \sim 4 \cdot 10^6$ 中查询长度至少为 $k$ 的连续一段 $0$ 的最小左端点。所有的修改操作都可以用线段树进行维护，询问操作则对线段树进行二分。
先定义线段树节点：
struct Node {
int l, r; // 维护区间的左右端点
int len; // 区间长度
int ls; // 区间左端点起往右连续一段0的长度
int rs; // 区间右端点起往左连续一段0的长度
int s; // 整个区间连续一段0的最大长度
}tr[N * 4];考虑 pushup 操作，假设要更新的节点 $u$ 的左右儿子分别是 $l$ 和 $r$。显然有 $u\mathrm{.ls} = l\mathrm{.ls}$，如果左儿子维护的区间全是 $0$，即 $l\mathrm{.ls} = l\mathrm{.len}$，那么还需要加上 $r\mathrm{.ls}$。同理有 $u\mathrm{.rs} = r\mathrm{.rs}$，如果右儿子维护的区间全是 $0$ 还要加上 $l\mathrm{.rs}$。最后是 $u\mathrm{.s}$，把分成三种情况，整段 $0$ 都在左儿子，该情况最长的一段 $0$ 是 $l\mathrm{.s}$；整段 $0$ 都在右儿子，该情况最长的一段 $0$ 是 $r\mathrm{.s}$；整段 $0$ 横跨左右儿子，该情况最长的一段 $0$ 是 $l\mathrm{.rs} + r\mathrm{.ls}$。
void pushup(int u) {
tr[u].ls = tr[u << 1].ls + (tr[u << 1].s == tr[u << 1].len) * tr[u << 1 | 1].ls;
tr[u].rs = tr[u << 1 | 1].rs + (tr[u << 1 | 1].s == tr[u << 1 | 1].len) * tr[u << 1].rs;
tr[u].s = max({tr[u << 1].s, tr[u << 1 | 1].s, tr[u << 1].rs + tr[u << 1 | 1].ls});
}修改操作就是基本的单点修改，其中如果要将下标 $x$ 置为 $c$，那么需要把维护该位置的节点的信息都置为 $\neg c$：
void modify(int u, int x, int c) {
if (tr[u].l == tr[u].r) {
tr[u].ls = tr[u].rs = tr[u].s = tr[u].len * !c;
}
else {
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, c);
else modify(u << 1 | 1, x, c);
pushup(u);
}
}最后是查询操作，因为要找到满足条件的最小的下标，因此先看看当前节点的左儿子 $l$ 是否存在长度至少为 $k$ 的一段 $0$，如果存在则递归到 $l$。否则看看横跨左右儿子的一段 $0$ 的长度是否至少为 $k$，如果满足则直接回传 $l\mathrm{.r} - l\mathrm{.rs} + 1$。最后再看看右儿子 $r$ 是否存在长度至少为 $k$ 的一段 $0$，存在则递归到 $r$（一定存在，因为维护的值域最大设到了 $4 \cdot 10^6$）。
int query(int u, int k) {
if (tr[u].l == tr[u].r) return tr[u].l;
if (tr[u << 1].s >= k) return query(u << 1, k);
if (tr[u << 1].rs + tr[u << 1 | 1].ls >= k) return tr[u << 1].r - tr[u << 1].rs + 1;
if (tr[u << 1 | 1].s >= k) return query(u << 1 | 1, k);
return 0;
}AC 代码如下，时间复杂度为 $O((n+m) \log{A})$：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 4e6 + 5;
struct Node {
int l, r, len, ls, rs, s;
}tr[N * 4];
void pushup(int u) {
tr[u].ls = tr[u << 1].ls + (tr[u << 1].s == tr[u << 1].len) * tr[u << 1 | 1].ls;
tr[u].rs = tr[u << 1 | 1].rs + (tr[u << 1 | 1].s == tr[u << 1 | 1].len) * tr[u << 1].rs;
tr[u].s = max({tr[u << 1].s, tr[u << 1 | 1].s, tr[u << 1].rs + tr[u << 1 | 1].ls});
}
void build(int u, int l, int r) {
tr[u] = {l, r, r - l + 1};
if (l == r) {
tr[u].ls = tr[u].rs = tr[u].s = 1;
}
else {
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int x, int c) {
if (tr[u].l == tr[u].r) {
tr[u].ls = tr[u].rs = tr[u].s = tr[u].len * !c;
}
else {
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, c);
else modify(u << 1 | 1, x, c);
pushup(u);
}
}
int query(int u, int k) {
if (tr[u].l == tr[u].r) return tr[u].l;
if (tr[u << 1].s >= k) return query(u << 1, k);
if (tr[u << 1].rs + tr[u << 1 | 1].ls >= k) return tr[u << 1].r - tr[u << 1].rs + 1;
if (tr[u << 1 | 1].s >= k) return query(u << 1 | 1, k);
return 0;
}
void solve() {
int n, m;
cin >> n;
set<int> st;
while (n--) {
int x;
cin >> x;
st.insert(x);
modify(1, x, 1);
}
cin >> m;
while (m--) {
char op;
int x;
cin >> op >> x;
if (op == '+') {
st.insert(x);
modify(1, x, 1);
}
else if (op == '-') {
st.erase(x);
modify(1, x, 0);
}
else {
cout << query(1, x) << ' ';
}
}
for (auto &x : st) {
modify(1, x, 0);
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
build(1, 1, N - 1);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
参考资料
Codeforces Round 966 (Div. 3) A - H：https://zhuanlan.zhihu.com/p/714360692
标签：10,set,int,tr,Ksyusha,le,Set,Loaded,mathrm From： https://www.cnblogs.com/onlyblues/p/18363455