可持久化平衡树
cpp
struct FHQ{
int ls,rs,key,sz,val;
} fhq[N*50];
int root[N],T1,T2,T3,idx;
int newNode(int val=0){
fhq[++idx]={0,0,(int)rng(),1,val};
return idx;
}
void pushup(int u){
fhq[u].sz=fhq[fhq[u].ls].sz+fhq[fhq[u].rs].sz+1;
}
void split(int u,int val,int &x,int &y){
if(!u){
x=y=0;
return;
}
if(fhq[u].val>val){
y=newNode();
fhq[y]=fhq[u];
split(fhq[y].ls,val,x,fhq[y].ls);
pushup(y);
}
else{
x=newNode();
fhq[x]=fhq[u];
split(fhq[x].rs,val,fhq[x].rs,y);
pushup(x);
}
}
int merge(int x,int y){
if(!x||!y)return x+y;
int u=newNode();
if(fhq[x].key>fhq[y].key){
fhq[u]=fhq[x];
fhq[u].rs=merge(fhq[u].rs,y);
pushup(u);
return u;
}
fhq[u]=fhq[y];
fhq[u].ls=merge(x,fhq[u].ls);
pushup(u);
return u;
}
void insert(int &root,int val){
split(root,val,T1,T2);
root=merge(merge(T1,newNode(val)),T2);
}
void erase(int &root,int x){
split(root,x,T1,T2);
split(T1,x-1,T1,T3);
T3=merge(fhq[T3].ls,fhq[T3].rs);
root=merge(merge(T1,T3),T2);
}
int find_rank(int &root,int x){
split(root,x-1,T1,T2);
int res=fhq[T1].sz+1;
root=merge(T1,T2);
return res;
}
int kth(int &root,int k){
int u=root;
while(u){
int tmp=fhq[fhq[u].ls].sz+1;
if(tmp==k)break;
if(k<tmp)u=fhq[u].ls;
else{
k-=tmp;
u=fhq[u].rs;
}
}
return fhq[u].val;
}
int find_prev(int u,int val){
if(u==0)return -INF;
if(fhq[u].val<val){
int res=find_prev(fhq[u].rs,val);
return res==-INF?fhq[u].val:res;
}
return find_prev(fhq[u].ls,val);
}
int find_next(int u,int val){
if(u==0)return INF;
if(fhq[u].val>val){
int res=find_next(fhq[u].ls,val);
return res==INF?fhq[u].val:res;
}
return find_next(fhq[u].rs,val);
}