http://www.lydsy.com/JudgeOnline/problem.php?id=3224
经典的平衡树模板题…各种平衡树好像都可以（黄学长之前好像还用vector卡过了这题）
所以这篇博客也就来存一下模板什么的…
如果发现有什么地方讲错的还请留言怼我
1.Treap
首先是经典的Treap：Treap=Tree+heap
这里每个结点有两个值$v$（结点的值）和$rnd$（一个随机值），叫Treap的原因也就是它遵循二叉查找树的性质（$o$的左子树的$v$<$o$的$v$<$o$右子树的$v$）和堆的性质（$o$左子树的$rnd$>$o$的$rnd$且$o$右子树的$rnd$>$o$的$rnd$，当然改成<也可以，不过这里我先统一用>方便说）
二叉查找树的性质在插入的时候直接维护：如果要插入的比当前小就丢给左孩子，大的话就丢给右孩子（相等的话就直接存这个点上，这里用一个变量$w$来记录这个点实际上有几个点）
堆的性质通过旋转操作来维护：
比如如果你发现$o$的左孩子的$rnd$比$o$的$rnd$小了，它应该比较大才对，那这时候就可以把$o$右旋让它的左孩子变成它的父亲，可以发现这样子做二叉搜索树的性质并没有被破坏，如果是右孩子$rnd$比$o$大的话同理就用左旋啦，靠这两个操作就完成了堆性质的维护。因为用的是随机数所以期望情况下效率还是不错的。
（建议配合图片食用）
其他操作都比较简单了…具体还是见代码吧
#include<cstdio> #include<cstdlib> #define rep(i,n) for(register int i=1;i<=n;i++) using namespace std; inline int read() { int s=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();} return s*f; } const int N=100005; struct tree { int s,w,rnd,l,r,v; }tr[N]; int n,rot,cnt,op; inline void updata(int x) { tr[x].s=tr[tr[x].l].s+tr[tr[x].r].s+tr[x].w; } inline void rturn(int &x) { int t=tr[x].l;tr[x].l=tr[t].r;tr[t].r=x; tr[t].s=tr[x].s;updata(x);x=t; } inline void lturn(int &x) { int t=tr[x].r;tr[x].r=tr[t].l;tr[t].l=x; tr[t].s=tr[x].s;updata(x);x=t; } inline void insert(int &k,int val) { if(k==0) { k=++cnt;tr[k].v=val;tr[k].w=tr[k].s=1; tr[k].rnd=rand();return; } tr[k].s++; if(tr[k].v==val) tr[k].w++; else if(tr[k].v<val) { insert(tr[k].r,val); if(tr[tr[k].r].rnd<tr[k].rnd)lturn(k); }else { insert(tr[k].l,val); if(tr[tr[k].l].rnd<tr[k].rnd)rturn(k); } } inline void del(int &k,int val) { if(k==0)return; if(tr[k].v==val) { if(tr[k].w>1) tr[k].w--,tr[k].s--; else { if(tr[k].l*tr[k].r==0) k=tr[k].l+tr[k].r; else if(tr[tr[k].l].rnd<tr[tr[k].r].rnd) rturn(k),del(k,val); else lturn(k),del(k,val); } }else if(tr[k].v<val) { tr[k].s--; del(tr[k].r,val); }else { tr[k].s--; del(tr[k].l,val); } } inline int query_number_rank(int k,int val) { if(k==0)return 0; if(tr[k].v==val) return tr[tr[k].l].s+1; else if(tr[k].v<val) return query_number_rank(tr[k].r,val)+tr[tr[k].l].s+tr[k].w; else return query_number_rank(tr[k].l,val); } inline void query_rank(int k,int x,int &ans) { if(k==0)return; if(x<=tr[tr[k].l].s) query_rank(tr[k].l,x,ans); else if(tr[tr[k].l].s+tr[k].w<x) query_rank(tr[k].r,x-tr[tr[k].l].s-tr[k].w,ans); else ans=tr[k].v; } inline void query_pre(int k,int x,int &ans) { if(k==0)return; if(tr[k].v<x) { ans=tr[k].v; query_pre(tr[k].r,x,ans); }else query_pre(tr[k].l,x,ans); } inline void query_sub(int k,int x,int &ans) { if(k==0)return; if(tr[k].v>x) { ans=tr[k].v; query_sub(tr[k].l,x,ans); }else query_sub(tr[k].r,x,ans); } int main() { srand(19260817); n=read(); rep(i,n) { int x,ans=0; op=read();x=read(); if(op==1) insert(rot,x); else if(op==2) del(rot,x); else if(op==3) printf("%d ",query_number_rank(rot,x)); else if(op==4) { query_rank(rot,x,ans); printf("%d ",ans); }else if(op==5) { query_pre(rot,x,ans); printf("%d ",ans); }else { query_sub(rot,x,ans); printf("%d ",ans); } } return 0; }
2.01Trie
别人博客的：http://www.cnblogs.com/KingSann/articles/7339563.html
有个神奇的东西叫01Trie…其实就是一颗字符集为${0,1 }$的Trie。
然后我们把要存的变量搞成二进制丢到这颗Trie里面就行了！非常好写。
缺点就是就是空间比较大，以及如果要存浮点数就有点无能为力了…（能不能写成$a*10^b$的形式丢树上呢…脑补ing…）
#include<cstdio> const int N=100005*33; const int T=(int)1e7;//偏移的大小 const int B=31; inline int read() { int s=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();} return s*f; } int n,cnt=1,x,op; int tr[N][2],f[N]; inline void insert(int val,int c) { int k=1;val+=T; for(register int i=B;~i;i--) { int t=(val>>i)&1; if(!tr[k][t])tr[k][t]=++cnt; k=tr[k][t];f[k]+=c; } } inline int rank(int val) { int k=1,res=0;val+=T; for(register int i=B;~i;i--) { int t=(val>>i)&1; if(t)res+=f[tr[k][0]]; k=tr[k][t]; } return res; } inline int kth(int val) { int k=1,res=0; for(register int i=B;~i;i--) { if(val>f[tr[k][0]])res|=(1<<i),val-=f[tr[k][0]],k=tr[k][1]; else k=tr[k][0]; } res-=T;return res; } int main() { n=read(); while(n--) { op=read();x=read(); if(op==1)insert(x,1); else if(op==2)insert(x,-1); else if(op==3)printf("%d ",rank(x)+1); else if(op==4)printf("%d ",kth(x)); else if(op==5)printf("%d ",kth(rank(x))); else if(op==6)printf("%d ",kth(rank(x+1)+1)); } return 0; }
先写到这了其他的有空再更…