@zzzc18
2017-10-23T18:04:24.000000Z
字数 1915
阅读 1144
模板库
Treap
[洛谷]普通平衡树
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int n;
const int MAXN = 100000+9;
struct T{
int val,RD,sz,ls,rs;
}tree[MAXN];
int root;
struct PAIR{
int first,second;
PAIR(){first=second=0;}
};
void update(int x){
tree[x].sz=tree[tree[x].ls].sz+tree[tree[x].rs].sz+1;
}
int New_Node(int x){//woooooooooooooooooooooooooooooo
static int cnt=0;
tree[++cnt].val=x;
tree[cnt].sz=1;
tree[cnt].RD=rand();
return cnt;
}
PAIR split(int x,int val){
PAIR re;
if(x==0){
return re;
}
if(val>=tree[x].val){
re=split(tree[x].rs,val);
tree[x].rs=re.first;
re.first=x;
update(x);
}
else{
re=split(tree[x].ls,val);
tree[x].ls=re.second;
re.second=x;
update(x);
}
return re;
}
int merge(int u,int v){
if(u==0 || v==0){
return u+v;
}
if(tree[u].RD<tree[v].RD){
tree[u].rs=merge(tree[u].rs,v);
update(u);
return u;
}
else{
tree[v].ls=merge(u,tree[v].ls);
update(v);
return v;
}
}
void insert(int val){
PAIR rt=split(root,val);
root=merge(rt.first,merge(New_Node(val),rt.second));
}
void del(int val){
PAIR lrt=split(root,val-1);
PAIR rrt=split(lrt.second,val);
rrt.first=merge(tree[rrt.first].ls,tree[rrt.first].rs);
root=merge(lrt.first,merge(rrt.first,rrt.second));
}
int n2r(int val){
PAIR rt=split(root,val-1);
int re=tree[rt.first].sz+1;
root=merge(rt.first,rt.second);
return re;
}
int r2n(int x,int val){
while(true){
if(tree[tree[x].ls].sz>=val){
x=tree[x].ls;
}
else if(tree[tree[x].ls].sz+1<val){
val-=tree[tree[x].ls].sz+1;
x=tree[x].rs;
}
else{
return tree[x].val;
}
}
}
int pred(int val){
PAIR rt=split(root,val-1);
int re=r2n(rt.first,tree[rt.first].sz);
root=merge(rt.first,rt.second);
return re;
}
int succ(int val){
PAIR rt=split(root,val);
int re=r2n(rt.second,1);
root=merge(rt.first,rt.second);
return re;
}
int main(){
scanf("%d",&n);
int i;
for(i=1;i<=n;i++){
int opt,x;
scanf("%d%d",&opt,&x);
if(opt==1)insert(x);
if(opt==2)del(x);
if(opt==3){printf("%d\n",n2r(x));}
if(opt==4){printf("%d\n",r2n(root,x));}
if(opt==5){printf("%d\n",pred(x));}
if(opt==6){printf("%d\n",succ(x));}
}
return 0;
}