P3369 【模板】普通平衡树 (fhq treap)
hhz6830975
2018-01-04 14:10:17
传送门：http://www.yhzq-blog.cc/fhq-treap%E6%80%BB%E7%BB%93/
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
const int maxn=100010;
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,Tcnt;
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];
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;}
else if(T[u].val<=k) x=u,split(T[u].son[1],k,T[u].son[1],y);
else y=u,split(T[u].son[0],k,x,T[u].son[0]);
pushup(u);
}
int merge(int x,int y){
if(!x||!y) return x+y;
else if(T[x].prio<T[y].prio){
T[x].son[1]=merge(T[x].son[1],y);
pushup(x);
return x;
}
else{
T[y].son[0]=merge(x,T[y].son[0]);
pushup(y);
return y;
}
}
inline void ins(int x){
int a,b;
split(root,x,a,b);
T[++Tcnt]=node(x);
root=merge(merge(a,Tcnt),b);
}
inline void del(int x){
int a,b,c;
split(root,x,a,b);
split(a,x-1,a,c);
root=merge(merge(a,merge(T[c].son[0],T[c].son[1])),b);
}
inline int rank(int x){
int a,b,ret;
split(root,x-1,a,b);
ret=T[a].size+1;
root=merge(a,b);
return ret;
}
inline int num(int x){
int u=root;
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 x){
int a,b;
split(root,x-1,a,b);
int u=a,ret;
while(T[u].son[1]) u=T[u].son[1];
ret=T[u].val;
root=merge(a,b);
return ret;
}
inline int nxt(int x){
int a,b;
split(root,x,a,b);
int u=b,ret;
while(T[u].son[0]) u=T[u].son[0];
ret=T[u].val;
root=merge(a,b);
return ret;
}
int main(){
srand(1);
n=read();
for(int i=1;i<=n;i++){
int op=read(),x=read();
switch(op){
case 1:{
ins(x);
break;
}
case 2:{
del(x);
break;
}
case 3:{
printf("%d\n",rank(x));
break;
}
case 4:{
printf("%d\n",num(x));
break;
}
case 5:{
printf("%d\n",pre(x));
break;
}
default:{
printf("%d\n",nxt(x));
break;
}
}
}
return 0;
}
```