P3835 【模板】可持久化平衡树
hhz6830975
2018-01-08 18:17:55
其实在fhq treap的基础上稍作修改就可以了
每split和merge到一个点都复制一个就ok
复制的地方见代码中标注
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
const int maxn=500010;
const int INF=2147483647;
int n;
inline int read(){
int ret=0,s=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') s=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {ret=ret*10+ch-'0'; ch=getchar();}
return ret*s;
}
int root[maxn],Tcnt,V;
struct node{
int son[2],val,prio,size;
node(){}
node(int x){son[0]=son[1]=0,val=x,prio=rand(),size=1;}
}T[maxn*50];
inline void pushup(int u){T[u].size=T[T[u].son[0]].size+T[T[u].son[1]].size+1;}
void split(int &u,int k,int &x,int &y){
if(!u) {x=y=0; return;}
T[++Tcnt]=T[u],u=Tcnt;//copy
if(T[u].val<=k) x=u,split(T[u].son[1],k,T[u].son[1],y),pushup(x);
else y=u,split(T[u].son[0],k,x,T[u].son[0]),pushup(y);
}
int merge(int x,int y){
if(!x||!y) return x+y;
else if(T[x].prio<T[y].prio){
T[++Tcnt]=T[x],x=Tcnt;//copy
T[x].son[1]=merge(T[x].son[1],y);
pushup(x);
return x;
}
else{
T[++Tcnt]=T[y],y=Tcnt;//copy
T[y].son[0]=merge(x,T[y].son[0]);
pushup(y);
return y;
}
}
inline void ins(int v,int x){
int a,b;
split(root[v],x,a,b);
T[++Tcnt]=node(x);
root[V]=merge(merge(a,Tcnt),b);
}
inline void del(int v,int x){
int a,b,c;
split(root[v],x,a,b);
split(a,x-1,a,c);
root[V]=merge(merge(a,merge(T[c].son[0],T[c].son[1])),b);
}
inline int rank(int v,int x){
int a,b,ret;
split(root[v],x-1,a,b);
ret=T[a].size+1;
root[V]=merge(a,b);
return ret;
}
inline int num(int v,int x){
int u=root[v];
root[V]=root[v];
while(1){
int lsize=T[T[u].son[0]].size;
if(x==lsize+1) return T[u].val;
else if(x<=lsize) u=T[u].son[0];
else u=T[u].son[1],x-=lsize+1;
}
}
inline int pre(int v,int x){
int a,b;
split(root[v],x-1,a,b);
int u=a,ret;
if(!u) ret=-INF;
else{
while(T[u].son[1]) u=T[u].son[1];
ret=T[u].val;
}
root[V]=merge(a,b);
return ret;
}
inline int nxt(int v,int x){
int a,b;
split(root[v],x,a,b);
int u=b,ret;
if(!u) ret=INF;
else{
while(T[u].son[0]) u=T[u].son[0];
ret=T[u].val;
}
root[V]=merge(a,b);
return ret;
}
int main(){
srand(1);
n=read();
for(int i=1;i<=n;i++){
int v=read(),op=read(),x=read();
++V;
switch(op){
case 1:{
ins(v,x);
break;
}
case 2:{
del(v,x);
break;
}
case 3:{
printf("%d\n",rank(v,x));
break;
}
case 4:{
printf("%d\n",num(v,x));
break;
}
case 5:{
printf("%d\n",pre(v,x));
break;
}
default:{
printf("%d\n",nxt(v,x));
break;
}
}
}
return 0;
}
```