题解 P3835 【【模板】可持久化平衡树】
GGN_2015
2018-09-29 19:54:11
”一道可持久化数据结构的题，如果不强制在线，那么它八成不是一道真正的可持久化数据结构的题。“ —— GGN_2015
惊奇地发现这道题其实并不需要任何可持久化数据结构。
我们只需要建立一颗”时光树“（我们暂且这样称呼它）。如果i时刻的平衡树是由$v_i$时刻发展而来的，那么我们就令”时光树“上i号结点的父亲为$v_i$。0号结点显然是整棵”时光树“的根结点。
维护一棵平衡树（我写的是treap），最开始的时候这是一棵空树。在”时光树“上DFS，每进入结点i时就在平衡树中进行操作i（修改数据结构或储存查询的结果），然后再依次DFS结点i的每个儿子。退出结点i时，就”撤销“这个结点对数据结构的修改。例如当$opt_i = 1$时，我们向数据结构中插入了元素$x_i$，离开结点i时，我们再把$x_i$从数据结构中删除。
比较特殊的是：当$opt_i = 2$时，删除是可能失败的。如果删除失败的话，我们在回溯的时候要特判（就是说不要把本就没被成功删除的$x_i$插入回数据结构中）。
附上代码之前先作出一个声明：我的treap的代码不支持可重集合，所以我用了一个类似pair的数据结构来储存元素（第一维存储元素的值，第二维记录操作的编号），这样可以保证treap中没有重复的元素。另外，我懒得写前去和后继的查询，所以我的”前驱“和”后继“查询是利用”排名“和”第k大“查询间接实现的。（我觉得这样写treap更好调试一些）
```cpp
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct item {int val, id;};
bool operator < (item A, item B) {
if(A.val != B.val) return A.val < B.val;
return A.id < B.id;
}
bool operator == (item A, item B) {
return A.val==B.val && A.id==B.id;
}
const int maxn = (500000 + 6)*2;
namespace treap {
int ch[maxn][2], rnd[maxn], siz[maxn]; item key[maxn]; int ncnt;
queue<int> Q;
void maintain(int x) {
siz[x] = 1 + siz[ch[x][0]] + siz[ch[x][1]];
}
int newnode() {
if(!Q.empty()) {
int x = Q.front(); Q.pop();
ch[x][0] = ch[x][1] = rnd[x] = siz[x] = 0; key[x] = (item){0, 0};
return x;
}
return ++ ncnt;
}
void rotate(int& x, int d) {
int k = ch[x][d^1]; ch[x][d^1] = ch[k][d]; ch[k][d] = x;
maintain(x); x = k; maintain(k);
}
void insert(int& x, item v) {
if(x == 0) {
x = newnode(); rnd[x] = rand(); siz[x] = 1; key[x] = v;
return;
}
int d = v < key[x] ? 0 : 1; insert(ch[x][d], v);
maintain(x);
if(rnd[x] > rnd[ch[x][d]]) rotate(x, d^1);
}
int rnk(int x, item v) {
if(x == 0) return 1;
int lsiz = 1 + siz[ch[x][0]];
if(v == key[x]) return lsiz;
if(v < key[x]) return rnk(ch[x][0], v);
else return rnk(ch[x][1], v) + lsiz;
}
item kth(int x, int k) {
if(x==0 || k<=0 || k>siz[x])
return k<=0 ? (item){-2147483647, 0} : (item){2147483647, 0};
int lsiz = 1 + siz[ch[x][0]];
if(lsiz == k) return key[x];
if(k < lsiz) return kth(ch[x][0], k);
else return kth(ch[x][1], k-lsiz);
}
int LSIZ(int x) {return 1 + siz[ch[x][0]];}
void erase(int& x, int k) {
if(x == 0) return; /// 删除元素时一定要特判检测是否相等
int lsiz = 1 + siz[ch[x][0]];
if(lsiz == k) {
if(ch[x][0]==0 || ch[x][1]==0) {
int tmp = x; x = ch[x][0] + ch[x][1]; Q.push(tmp);
ch[tmp][0] = ch[tmp][1] = siz[tmp] = rnd[tmp] = 0;
key[tmp] = (item){0, 0};
}else {
if(rnd[ch[x][0]] > rnd[ch[x][1]]) {
rotate(x, 0); erase(ch[x][0], LSIZ(ch[x][0]));
}else {
rotate(x, 1); erase(ch[x][1], LSIZ(ch[x][1]));
}
maintain(x);
}
return;
}else {
if(k < lsiz) erase(ch[x][0], k);
else erase(ch[x][1], k-lsiz);
maintain(x);
}
}
}
int root = 0, V[maxn], OPT[maxn], X[maxn], ANS[maxn];
namespace tree {
vector<int> nxt[maxn];
void addedge(int f, int t) {nxt[f].push_back(t);}
void dfs(int x) {
bool delsuc = 0; /// 记录删除操作是否成功
if(OPT[x]) { /// 有操作
if(OPT[x] == 1) { /// 插入一个元素
treap::insert(root, (item){X[x], x});
}else if(OPT[x] == 2) { /// 删除一个元素
int rnk = treap::rnk(root, (item){X[x], 0}); /// 查询这个元素的排名
int get = treap::kth(root, rnk).val; /// 得到这个元素(可能为+-inf)
if(get == X[x]) { /// 可以删除
treap::erase(root, rnk); delsuc = 1;
}
}else if(OPT[x] == 3) { /// 查排名
ANS[x] = treap::rnk(root, (item){X[x], 0});
}else if(OPT[x] == 4) { /// 查第k大
ANS[x] = treap::kth(root, X[x]).val;
}else if(OPT[x] == 5) { /// prev
int rnk = treap::rnk(root, (item){X[x], 0}) - 1;
int get = treap::kth(root, rnk).val;
ANS[x] = get;
}else if(OPT[x] == 6) { /// next
int rnk = treap::rnk(root, (item){X[x], 0x7f7f7f7f});
int get = treap::kth(root, rnk).val;
ANS[x] = get;
}
}
for(int i = 0; i < (int)nxt[x].size(); i ++) {
int t = nxt[x][i]; dfs(t); /// 递归计算
}
if(OPT[x] == 1) { /// 回滚插入操作
int rnk = treap::rnk(root, (item){X[x], 0}); /// 一定有
treap::erase(root, rnk);
}
if(OPT[x]==2 && delsuc) {
treap::insert(root, (item){X[x], x});
}
}
}
int main() {
//freopen("nontime.in", "r", stdin);
int n; scanf("%d", &n);
for(int i = 1; i <= n; i ++) {
scanf("%d%d%d", &V[i], &OPT[i], &X[i]);
tree::addedge(V[i], i);
}
tree::dfs(0);
for(int i = 1; i <= n; i ++) {
if(OPT[i]>=3) {
printf("%d\n", ANS[i]);
}
}
return 0;
}
```