模版题目
普通平衡树:
luogu3369
luogu6136
splay:
luogu3391
Treap
treap实现的平衡树,需要定义maxn
luogu6136 7.27s(无内存回收) 9.24s(内存回收)
struct node{
int s,v,r;
node*ch[2];
inline void maintain(){
s=ch[0]->s+ch[1]->s+1;
}
};
struct treap{
node pool[maxn],*root,*null;
queue<node*>Q;
treap(){
init();
}
node*newnode(int x){
node*pt=Q.front();
Q.pop();
pt->s=1;pt->ch[0]=pt->ch[1]=null;
pt->r=rand()*rand();
pt->v=x;
return pt++;
}
void rot(node*&o,int d){
node*t=o->ch[d^1];
o->ch[d^1]=t->ch[d];t->ch[d]=o;
o->maintain();t->maintain();
o=t;
}
void insert(node*&o,int x){
if(o==null) o=newnode(x);
else{
if(x<o->v){
insert(o->ch[0],x);
if(o->ch[0]->r>o->r) rot(o,1);
}else{
insert(o->ch[1],x);
if(o->ch[1]->r>o->r) rot(o,0);
}
}
o->maintain();
}
void del(node*&o,int x){
if(o->v==x){
if(o->ch[0]!=null&&o->ch[1]!=null){
if(o->ch[0]->r>o->ch[1]->r){
rot(o,1);del(o->ch[1],x);
}else{
rot(o,0);del(o->ch[0],x);
}
}else if(o->ch[0]!=null){
Q.push(o);
o=o->ch[0];
}else{
Q.push(o);
o=o->ch[1];
}
}else{
if(x<o->v) del(o->ch[0],x);
else del(o->ch[1],x);
}
if(o!=null) o->maintain();
}
int rank(node*o,int x){
if(o==null) return 1;
if(x==o->v) return min(rank(o->ch[0],x),o->ch[0]->s+1);
if(x<o->v) return rank(o->ch[0],x);
return rank(o->ch[1],x)+o->ch[0]->s+1;
}
int num(node*o,int x){
if(x==o->ch[0]->s+1) return o->v;
if(x<=o->ch[0]->s) return num(o->ch[0],x);
return num(o->ch[1],x-o->ch[0]->s-1);
}
int pre(node*o,int x){
if(o==null) return -inf;
return x<=o->v?pre(o->ch[0],x):max(o->v,pre(o->ch[1],x));
}
int suc(node*o,int x){
if(o==null) return inf;
return x>=o->v?suc(o->ch[1],x):min(o->v,suc(o->ch[0],x));
}
void init(){
srand(time(NULL));
for(int i=0;i<maxn;i++)
Q.push(pool+i);
null=newnode(0);
null->s=null->r=0;
root=null;
}
};