\(\text{luogu-3369}\)
您需要动态地维护一个可重集合 \(M\)，并且提供以下操作：
- 向 \(M\) 中插入一个数 \(x\)。
- 从 \(M\) 中删除一个数 \(x\)（若有多个相同的数，应只删除一个）。
- 查询 \(M\) 中有多少个数比 \(x\) 小，并且将得到的答案加一。
- 查询如果将 \(M\) 从小到大排列后，排名位于第 \(x\) 位的数。
- 查询 \(M\) 中 \(x\) 的前驱（前驱定义为小于 \(x\)，且最大的数）。
- 查询 \(M\) 中 \(x\) 的后继（后继定义为大于 \(x\)，且最小的数）。
对于操作 \(3,5,6\)，不保证当前可重集中存在数 \(x\)。
对于操作 \(5,6\)，保证答案一定存在。
\(1\le n \le 10^5\)，\(|x| \le 10^7\)。
平衡树模板题。这里介绍用 Treap 实现平衡树。
首先 Treap 是一棵拥有键值和优先级两种权值的树。
对于键值而言，这棵树就是 BST（排序二叉树）；对于优先级而言，这棵树就是一个堆，即在这棵树的任意子树种，根节点的优先级是最大的（这个性质称为堆性质）。
不难证明，如果每个节点的优先级事先给定的且互不相等，整棵树的形态也就唯一确定了，和元素的插入顺序无关。在 Treap 的插入算法中，每个节点的优先级是随机确定的，因此各操作的时间复杂度也是随机的。幸运的是，可以证明插入、删除和查找的期望时间复杂度均为 \(O(\log n)\)。
这些都是 Treap 的概况，下面是节点需要记录的数据：
- 左右儿子编号 \(l_x,r_x\)，因为实际上 Treap 是动态开点的。
- 键值 \(v_x\)、随机分配的优先级 \(rd_x\)。
- 权重 \(w_x\)，因为本题是可重集，所以相同的数我们压到一个点中。
- 子树大小 \(sz_x\)，查询操作需要用到。
插入操作。
根据 BST 的性质，插入的数 \(x\) 有唯一的地方插入。找到插入位置后分配优先级、节点编号等。
此时优先级分配并不一定满足堆性质，于是我们需要动态调整。
这里就用到了左旋、右旋，即把整棵子树的根节点旋转为右儿子或左儿子。
以左旋举例，需要的操作顺序大致如下，令旋转根节点为 \(p\)：
- 令 \(k \gets r_p\)，记录下来 \(p\) 节点的右子树。
- \(r_p \gets l_k\)，将 \(k\) 的左子树（即 \(p\) 的右子树的左子树）挂到 \(p\) 的右子树上。
- \(l_k \gets p\)，将 \(p\) 挂到 \(k\) 的左子树上。
- \(sz_k \gets sz_p\)，更新 \(sz\) 信息，即把新根的 \(sz\) 赋值为原根的 \(sz\)。
- \(sz_p \gets sz_{l_p} + sz_{r_p} + w_p\)，更新原根的 \(sz\) 值。
- \(p \gets k\)，换根。
大概就是这样：
void pushup(ll x) { sz[x] = sz[l[x]] + sz[r[x]] + w[x]; return; }
void left(ll &p) {ll k = r[p]; r[p] = l[k], l[k] = p;sz[k] = sz[p], pushup(p), p = k;return;
}
void right(ll &p) {ll k = l[p]; l[p] = r[k], r[k] = p;sz[k] = sz[p], pushup(p), p = k;return;
}
那么插入操作就很好写了，注意细节：
void insert(ll &p, ll x) {if(!p) {p = (++ cnt), sz[p] = 1, w[p] = 1;v[p] = x, rd[p] = rnd(); return;}sz[p] ++;if(v[p] == x) w[p] ++;else if(v[p] < x) {insert(r[p], x);if(rd[r[p]] < rd[p]) left(p);}else {insert(l[p], x);if(rd[l[p]] < rd[p]) right(p);}return;
}
删除操作。
先找到要删除的数 \(x\) 的位置，如果不存在就返回删除失败。
找到之后，令 \(x\) 的编号为 \(p\)，分为下面几种情况：
- 若 \(w_p \ge 2\)，那么删除一个 \(x\) 之后并不会影响树的形态，直接更新 \(w_p,sz_p\) 即可，返回删除成功。
- 若 \(p\) 只有一个子树，那么直接让儿子节点代替 \(p\) 即可，返回删除成功。
- 否则，分为两种情况：
- 若 \(rd_{l_p} < rd_{r_p}\)，即 \(p\) 的右儿子优先级高，则左旋一下继续递归。
- 否则右旋一下继续递归。
代码如下：
bool del(ll &p, ll x) {if(!p) return 0;bool fg;if(v[p] == x) {if(w[p] > 1) { w[p] --, sz[p] --; return 1; }if(!l[p] || !r[p]) { p = l[p] + r[p]; return 1; }else if(rd[l[p]] < rd[r[p]]) { left(p); return del(p, x); }else { right(p); return del(p, x); }}else if(v[p] < x) {fg = del(r[p], x); if(fg) sz[p] --;return fg;}fg = del(l[p], x); if(fg) sz[p] --;return fg;
}
询问 \(x\) 的排名。
直接递归找即可，注意题目要求询问小于 \(x\) 的个数加一。
ll qryrk(ll p, ll x) {if(!p) return 1; // 注意此时询问的 x 不存在，但仍要加一，所以返回 1。if(v[p] == x) return sz[l[p]] + 1;if(v[p] < x) return sz[l[p]] + w[p] + qryrk(r[p], x);return qryrk(l[p], x);
}
询问排名 \(x\) 的数。
和上面的操作类似。
ll qrynum(ll p, ll x) {if(!p) return 0;if(x <= sz[l[p]]) return qrynum(l[p], x);if(x > sz[l[p]] + w[p]) return qrynum(r[p], x - sz[l[p]] - w[p]);return v[p];
}
查询 \(x\) 的前驱。
实际上是个类似二分的东西，一直更新答案，最终答案记录的就是最后一个小于 \(x\) 的数的编号。
void qrypre(ll p, ll x) {if(!p) return;if(v[p] < x) res = p, qrypre(r[p], x);else qrypre(l[p], x);
}
查询 \(x\) 的后继。
和上面的操作类似。
void qrysub(ll p, ll x) {if(!p) return;if(v[p] > x) res = p, qrysub(l[p], x);else qrysub(r[p], x);
}
于是汇总一下就变成了这样：
#include<iostream>
#include<cstdio>
#include<ctime>
#include<random>
using namespace std;
#define MAXN 100005
#define ll long long long long read() {long long x = 0, f = 1;char c = getchar();while(c > 57 || c < 48) { if(c == 45) f = -1; c = getchar(); }while(c >= 48 && c <= 57) { x = (x << 1) + (x << 3) + (c - 48); c = getchar(); }return x * f;
}mt19937 rnd(time(0));
ll n, op, x;struct Treap {ll l[MAXN], r[MAXN], v[MAXN], w[MAXN], sz[MAXN], rd[MAXN];ll cnt, res, rt;void pushup(ll x) { sz[x] = sz[l[x]] + sz[r[x]] + w[x]; return; }void left(ll &p) {ll k = r[p]; r[p] = l[k], l[k] = p;sz[k] = sz[p], pushup(p), p = k;return;}void right(ll &p) {ll k = l[p]; l[p] = r[k], r[k] = p;sz[k] = sz[p], pushup(p), p = k;return;}void insert(ll &p, ll x) {if(!p) {p = (++ cnt), sz[p] = 1, w[p] = 1;v[p] = x, rd[p] = rnd(); return;}sz[p] ++;if(v[p] == x) w[p] ++;else if(v[p] < x) {insert(r[p], x);if(rd[r[p]] < rd[p]) left(p);}else {insert(l[p], x);if(rd[l[p]] < rd[p]) right(p);}return;}bool del(ll &p, ll x) {if(!p) return 0;bool fg;if(v[p] == x) {if(w[p] > 1) { w[p] --, sz[p] --; return 1; }if(!l[p] || !r[p]) { p = l[p] + r[p]; return 1; }else if(rd[l[p]] < rd[r[p]]) { left(p); return del(p, x); }else { right(p); return del(p, x); }}else if(v[p] < x) {fg = del(r[p], x); if(fg) sz[p] --;return fg;}fg = del(l[p], x); if(fg) sz[p] --;return fg;}ll qryrk(ll p, ll x) {if(!p) return 1;if(v[p] == x) return sz[l[p]] + 1;if(v[p] < x) return sz[l[p]] + w[p] + qryrk(r[p], x);return qryrk(l[p], x);}ll qrynum(ll p, ll x) {if(!p) return 0;if(x <= sz[l[p]]) return qrynum(l[p], x);if(x > sz[l[p]] + w[p]) return qrynum(r[p], x - sz[l[p]] - w[p]);return v[p];}void qrypre(ll p, ll x) {if(!p) return;if(v[p] < x) res = p, qrypre(r[p], x);else qrypre(l[p], x);}void qrysub(ll p, ll x) {if(!p) return;if(v[p] > x) res = p, qrysub(l[p], x);else qrysub(r[p], x);}
} T;int main() {n = read();while(n --) {op = read(), x = read();if(op == 1) T.insert(T.rt, x);else if(op == 2) T.del(T.rt, x);else if(op == 3) cout << T.qryrk(T.rt, x) << "\n";else if(op == 4) cout << T.qrynum(T.rt, x) << "\n";else if(op == 5) {T.res = 0, T.qrypre(T.rt, x);cout << T.v[T.res] << "\n";}else {T.res = 0, T.qrysub(T.rt, x);cout << T.v[T.res] << "\n";}}return 0;
}
\(\text{luogu-6136}\)
您需要动态地维护一个可重集合 \(M\)，并且提供以下操作：
- 向 \(M\) 中插入一个数 \(x\)。
- 从 \(M\) 中删除一个数 \(x\)（若有多个相同的数，应只删除一个）。
- 查询 \(M\) 中有多少个数比 \(x\) 小，并且将得到的答案加一。
- 查询如果将 \(M\) 从小到大排列后，排名位于第 \(x\) 位的数。
- 查询 \(M\) 中 \(x\) 的前驱（前驱定义为小于 \(x\)，且最大的数）。
- 查询 \(M\) 中 \(x\) 的后继（后继定义为大于 \(x\)，且最小的数）。
本题强制在线，保证所有操作合法（操作 \(2\) 保证存在至少一个 \(x\)，操作 \(4,5,6\) 保证存在答案）。
我们记 \(\text{last}\) 表示上一次 \(3,4,5,6\) 操作的答案，则每次操作的 \(x'\) 都要异或上 \(\text{last}\) 才是真实的 \(x\)。初始 \(\text{last}\) 为 \(0\)。
\(1\leq n\leq 10^5\)，\(1\leq m\leq 10^6\)，\(0\leq a_i,x\lt 2^{30}\)。
只需要在上一题的模板上稍微修改即可，注意节点数最大为 \(1.1 \times 10^6\) 个。
主函数如下：
int main() {n = read(), m = read();for(int i = 1; i <= n; i ++) T.insert(T.rt, read());while(m --) {op = read(), x = read() ^ lst;if(op == 1) T.insert(T.rt, x);else if(op == 2) T.del(T.rt, x);else if(op == 3) ans ^= (lst = T.qryrk(T.rt, x));else if(op == 4) ans ^= (lst = T.qrynum(T.rt, x));else if(op == 5) T.res = 0, T.qrypre(T.rt, x), ans ^= (lst = T.v[T.res]);else T.res = 0, T.qrysub(T.rt, x), ans ^= (lst = T.v[T.res]);}cout << ans << "\n";return 0;
}