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
#include
#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].v1)
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].rndx)
{
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\n",query_number_rank(rot,x));
else if(op==4)
{
query_rank(rot,x,ans);
printf("%d\n",ans);
}else if(op==5)
{
query_pre(rot,x,ans);
printf("%d\n",ans);
}else
{
query_sub(rot,x,ans);
printf("%d\n",ans);
}
}
return 0;
}

2.01Trie

别人博客的：http://www.cnblogs.com/KingSann/articles/7339563.html

有个神奇的东西叫01Trie…其实就是一颗字符集为$\{0,1 \}$的Trie。

然后我们把要存的变量搞成二进制丢到这颗Trie里面就行了！非常好写。

缺点就是就是空间比较大，以及如果要存浮点数就有点无能为力了…（能不能写成$a*10^b$的形式丢树上呢…脑补ing…）

#include
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\n",rank(x)+1);
else if(op==4)printf("%d\n",kth(x));
else if(op==5)printf("%d\n",kth(rank(x)));
else if(op==6)printf("%d\n",kth(rank(x+1)+1));
}
return 0;
}

先写到这了其他的有空再更…