平衡树模板集合
codesonic
2018-07-11 13:59:53
自己存着用的
# WBLT
210ms / 6792kb
长度：2.4KB
```cpp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=400010;
const int ratio=5;
int n,cnt,fa,root;
int size[maxn],ls[maxn],rs[maxn],val[maxn];
inline void newnode(int &cur,int v){
cur=++cnt;
size[cur]=1;
val[cur]=v;
}
inline void copynode(int x,int y){
size[x]=size[y];
ls[x]=ls[y],rs[x]=rs[y];
val[x]=val[y];
}
inline void merge(int l,int r){
size[++cnt]=size[l]+size[r];
val[cnt]=val[r];
ls[cnt]=l,rs[cnt]=r;
}
inline void rotate(int cur,bool flag){
if(flag){
merge(ls[cur],ls[rs[cur]]);
ls[cur]=cnt;
rs[cur]=rs[rs[cur]];
}
else{
merge(rs[ls[cur]],rs[cur]);
rs[cur]=cnt;
ls[cur]=ls[ls[cur]];
}
}
inline void maintain(int cur){
if(size[ls[cur]]>size[rs[cur]]*ratio)
rotate(cur,0);
else if(size[rs[cur]]>size[ls[cur]]*ratio)
rotate(cur,1);
}
inline void pushup(int cur){
if(!size[ls[cur]])return ;
size[cur]=size[ls[cur]]+size[rs[cur]];
val[cur]=val[rs[cur]];
}
inline int minn(int a,int b){
return a<b?a:b;
}
inline int maxx(int a,int b){
return a>b?a:b;
}
inline void insert(int cur,int x){
if(size[cur]==1){
newnode(ls[cur],minn(x,val[cur]));
newnode(rs[cur],maxx(x,val[cur]));
pushup(cur);
return ;
}
maintain(cur);
insert(x>val[ls[cur]]?rs[cur]:ls[cur],x);
pushup(cur);
}
inline void erase(int cur,int x){
if(size[cur]==1){
cur= ls[fa]==cur?rs[fa]:ls[fa];
copynode(fa,cur);
return ;
}
maintain(cur);
fa=cur;
erase(x>val[ls[cur]]?rs[cur]:ls[cur],x);
pushup(cur);
}
inline int find(int cur,int x){
if(size[cur]==x)
return val[cur];
maintain(cur);
if(x>size[ls[cur]])
return find(rs[cur],x-size[ls[cur]]);
return find(ls[cur],x);
}
inline int rnk(int cur,int x){
if(size[cur]==1)
return 1;
maintain(cur);
if(x>val[ls[cur]])
return rnk(rs[cur],x)+size[ls[cur]];
return rnk(ls[cur],x);
}
int main(){
scanf("%d",&n);
newnode(root,(1<<30));
while(n--){
int s,x;
scanf("%d%d",&s,&x);
if(s==1)insert(root,x);
if(s==2)erase(root,x);
if(s==3)printf("%d\n",rnk(root,x));
if(s==4)printf("%d\n",find(root,x));
if(s==5)printf("%d\n",find(root,rnk(root,x)-1));
if(s==6)printf("%d\n",find(root,rnk(root,x+1)));
}
return 0;
}
```
# 旋转treap
252ms / 3.2MB
长度：2.35KB
```
#include<cstdio>
#include<iostream>
#include<algorithm>
#define maxn 100005
#define INF (1<<30)
int n;
struct treap{
int l[maxn],r[maxn],val[maxn],rnd[maxn],size[maxn],w[maxn];
int sz,ans,rt;
inline void pushup(int x){
size[x]=size[l[x]]+size[r[x]]+w[x];
}
void lrotate(int &k){
int t=r[k];
r[k]=l[t];
l[t]=k;
size[t]=size[k];
pushup(k);
k=t;
}
void rrotate(int &k){
int t=l[k];
l[k]=r[t];
r[t]=k;
size[t]=size[k];
pushup(k);
k=t;
}
void insert(int &k,int x){
if(!k){
sz++;k=sz;size[k]=1;w[k]=1;val[k]=x;
rnd[k]=rand();return;
}
size[k]++;
if(val[k]==x){
w[k]++;
}
else if(val[k]<x){
insert(r[k],x);
if(rnd[r[k]]<rnd[k])
lrotate(k);
}
else {
insert(l[k],x);
if(rnd[l[k]]<rnd[k])
rrotate(k);
}
}
void del(int &k,int x){
if(!k)return ;
if(val[k]==x){
if(w[k]>1){
w[k]--;
size[k]--;
return ;
}
if(l[k]==0||r[k]==0)
k=l[k]+r[k];
else if(rnd[l[k]]<rnd[r[k]]){
rrotate(k);
del(k,x);
}
else{
lrotate(k);
del(k,x);
}
}
else if(val[k]<x){
size[k]--;
del(r[k],x);
}
else {
size[k]--;
del(l[k],x);
}
}
int queryrank(int k,int x){
if(!k)
return 0;
if(val[k]==x)
return size[l[k]]+1;
else if(x>val[k]){
return size[l[k]]+w[k]+queryrank(r[k],x);
}
else return queryrank(l[k],x);
}
int querynum(int k,int x){
if(!k) return 0;
if(x<=size[l[k]]) return querynum(l[k],x);
else if(x>size[l[k]]+w[k])
return querynum(r[k],x-size[l[k]]-w[k]);
else return val[k];
}
void querypre(int k,int x){
if(!k) return ;
if(val[k]<x) ans=k,querypre(r[k],x);
else querypre(l[k],x);
}
void querysub(int k,int x){
if(!k) return ;
if(val[k]>x) ans=k,querysub(l[k],x);
else querysub(r[k],x);
}
}T;
int main()
{
scanf("%d",&n);
int opt,x;
for(int i=1;i<=n;i++){
scanf("%d%d",&opt,&x);
if(opt==1)T.insert(T.rt,x);
else if(opt==2)T.del(T.rt,x);
else if(opt==3){
printf("%d\n",T.queryrank(T.rt,x));
}
else if(opt==4){
printf("%d\n",T.querynum(T.rt,x));
}
else if(opt==5){
T.ans=0;
T.querypre(T.rt,x);
printf("%d\n",T.val[T.ans]);
}
else if(opt==6){
T.ans=0;
T.querysub(T.rt,x);
printf("%d\n",T.val[T.ans]);
}
}
return 0;
}
```
# fhq treap
572ms / 2.65MB
长度：2.13KB C++
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=500010;
int n,m,x,y,z,tot,opt;
struct fhq_treap{
int rnd[maxn],sum[maxn],size[maxn],ls[maxn],rs[maxn],root,tmp;
inline void build(int &x,int delta){
rnd[x=++tot]=rand()<<15|rand();
sum[x]=delta;
size[x]=1;
}
inline void up(int x){
if(!x) return ;
size[x]=size[ls[x]]+size[rs[x]]+1;
}
void merge(int &x,int l,int r){
if(!l||!r) x=l+r;
else if(rnd[l]<rnd[r]) x=l,merge(rs[x],rs[x],r),up(x);
else x=r,merge(ls[x],l,ls[x]),up(x);
}
void split(int x,int &l,int &r,int k){
if(!k) l=0,r=x;
else if(k==size[x]) l=x,r=0;
else if(k<=size[ls[x]]) r=x,split(ls[x],l,ls[x],k),up(x);
else l=x,split(rs[x],rs[x],r,k-size[ls[x]]-1),up(x);
}
int rank(int x,int w){
if(!x) return 0;
if(sum[x]>=w) return rank(ls[x],w);
return rank(rs[x],w)+size[ls[x]]+1;
}
inline void insert(int delta){
int x,y,rk=rank(root,delta);
split(root,x,y,rk);
build(tmp,delta);
merge(x,x,tmp);
merge(root,x,y);
}
inline void del(int delta){
int x,y,z,rk=rank(root,delta)+1;
split(root,x,y,rk);
split(x,x,z,rk-1);
merge(root,x,y);
}
inline int find(int delta)
{
int x,y,z,ans;
split(root,x,y,delta);
split(x,z,x,delta-1);
ans=sum[x];
merge(x,z,x);
merge(root,x,y);
return ans;
}
inline int pre(int delta){
int x,y,z,ans,rk=rank(root,delta);
split(root,x,y,rk);
split(x,z,x,rk-1);
ans=sum[x];
merge(x,z,x);
merge(root,x,y);
return ans;
}
inline int sub(int delta){
int x,y,z,ans,rk=rank(root,delta+1);
split(root,x,y,rk+1);
split(x,z,x,rk);
ans=sum[x];
merge(x,z,x);
merge(root,x,y);
return ans;
}
}T;
int main()
{
srand(19260817);
scanf("%d",&n);
T.rnd[0]=T.sum[0]=(1<<30);
while(n--){
int opt;
scanf("%d%d",&opt,&x);
if(opt==1) T.insert(x);
else if(opt==2) T.del(x);
else if(opt==3)printf("%d\n",T.rank(T.root,x)+1);
else if(opt==4)printf("%d\n",T.find(x));
else if(opt==5)printf("%d\n",T.pre(x));
else printf("%d\n", T.sub(x));
}
}
```