题解 P3369 【【模板】普通平衡树（Treap/SBT）】

这里给一种非旋转Treap的详细教程 建议有了splay的基础再看这个教程 反对楼下说非旋转Treap慢，实地测试比splay快很多 想学更多Treap的姿势欢迎来[博客](http://www.yhzq-blog.cc/fhq-treap总结/) 首先Orz fhq %%%%% 何为Treap Treap是一种二叉平衡树。Treap=BST+Heap Treap比较好玩的一点是，它整体是拥有二叉搜索树的性质，但是它的每一个节点都会有一个**附加权值**，它的附加权值是符合堆的性质。 这样我们可以明显看出，这棵树的形态(平衡与否)是由这个**附加权值**决定的。 那我们该如何取这个权值呢？**随机！！** 是的，我们每次都随机一个权值作为它的附加权值，那么它就\*大概\*是平衡的。 但是一般的平衡树都会有很恼人的旋转，又不好写，又不好调。 这里就郑重推出：**fhq treap!** 只需要两个基础操作，就可以达到splay的所有功能 ### 1： ￥split￥  它的主要思想就是把一个Treap分成两个。 split操作有两种类型，一种是按照权值分配，一种是按前k个分配。 第一种就是把所有小于k的权值的节点分到一棵树中，第二种是把前k个分到一个树里。 权值版： ```cpp void split(int now,int k,int &x,int &y) { if (!now) x=y=0; else { if (val[now]<=k) x=now,split(ch[now][1],k,ch[now][1],y); else y=now,split(ch[now][0],k,x,ch[now][0]); update(now); } } ``` 对于我们遍历到每一个点，假如它的权值小于k，那么它的所有左子树，都要分到左边的树里，然后遍历它的右儿子。假如大于k，把它的所有右子树分到右边的树里，遍历左儿子。 因为它的最多操作次数就是一直分到底，效率就是$O(\log n)$。 对于前k个版的，就是像找第k大的感觉。每次减掉siz ```cpp void split(int now,int k,int &x,int &y) { if (!now) x=y=0; else { if (k<=siz[ch[now][0]]) y=now,split(ch[now][0],k,x,ch[now][0]); else x=now,split(ch[now][1],k-siz[ch[now][0]]-1,ch[now][1],y); update(now); } } ``` ### 2： $merge$ 这个就是把两个Treap合成一个，保证第一个的权值小于第二个。  因为第一个Treap的权值都比较小，我们比较一下它的tar(附加权值)，假如第一个的tar小，我们就可以直接保留它的所有左子树，接着把第一个Treap变成它的右儿子。反之，我们可以保留第二棵的所有右子树，指针指向左儿子。 你可以把这个过程形象的理解为在第一个Treap的左子树上插入第二个树，也可以理解为在第二个树的左子树上插入第一棵树。因为第一棵树都满足小于第二个树，所以就变成了比较tar来确定树的形态。 也就是说，我们其实是遍历了第一个trep的根->最大节点，第二个Treap的根->最小节点，也就是$O(\log n)$ 代码： ```cpp int merge(int x,int y) { if (!x || !y) return x+y; if (pri[x]<pri[y]) { ch[x][1]=merge(ch[x][1],y); update(x); return x; } else { ch[y][0]=merge(x,ch[y][0]); update(y); return y; } } ``` 下面我们就可以通过这两个基本的东西实现各种各样的操作了。 ### 3：$insert$ 插入一个权值为v的点，把树按照v的权值split成两个，再按照顺序merge回去。 ```cpp split(root,v,x,y); root=merge(merge(x,new_node(v)),y); ``` ### 4： $del$ 删除权值为v的点，把树按照v分成两个a,b,再把a按照v-1分成c,d。把c的两个子儿子merge起来，再merge(merge(c,d),b) ```cpp split(root,v,x,z); split(x,v-1,x,y); y=merge(ch[y][0],ch[y][1]); root=merge(merge(x,y),z); ``` ### 5： $precursor$ 找前驱的话把root按v-1 split成x,y，在x里面找最大值 ### 6： $successor$ 找后继的话把root按v split成x,y，在y里找最小值 ### 7： $rank$ 把root按v-1 split成x,y，排名是x的siz 代码 ```cpp #include <cstdio> #include <cstdlib> #include <ctime> #define N 500005 using namespace std; int inline read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int ch[N][2],val[N],pri[N],siz[N],sz; void update(int x){siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]];} int new_node(int v) { siz[++sz]=1; val[sz]=v; pri[sz]=rand(); return sz; } int merge(int x,int y) { if (!x || !y) return x+y; if (pri[x]<pri[y]) { ch[x][1]=merge(ch[x][1],y); update(x); return x; } else { ch[y][0]=merge(x,ch[y][0]); update(y); return y; } } void split(int now,int k,int &x,int &y) { if (!now) x=y=0; else { if (val[now]<=k) x=now,split(ch[now][1],k,ch[now][1],y); else y=now,split(ch[now][0],k,x,ch[now][0]); update(now); } } int kth(int now,int k) { while(1) { if (k<=siz[ch[now][0]]) now=ch[now][0]; else if (k==siz[ch[now][0]]+1) return now; else k-=siz[ch[now][0]]+1,now=ch[now][1]; } } main() { srand((unsigned)time(NULL)); int T,com,x,y,z,a,b,root=0; scanf("%d",&T); while(T--) { com=read(),a=read(); if (com==1) { split(root,a,x,y); root=merge(merge(x,new_node(a)),y); } else if (com==2) { split(root,a,x,z); split(x,a-1,x,y); y=merge(ch[y][0],ch[y][1]); root=merge(merge(x,y),z); } else if (com==3) { split(root,a-1,x,y); printf("%d\n",siz[x]+1); root=merge(x,y); } else if (com==4) printf("%d\n",val[kth(root,a)]); else if (com==5) { split(root,a-1,x,y); printf("%d\n",val[kth(x,siz[x])]); root=merge(x,y); } else { split(root,a,x,y); printf("%d\n",val[kth(y,1)]); root=merge(x,y); } } } ```