题解 P3369 【【模板】普通平衡树（Treap/SBT）】
litble
2017-07-10 13:55:45
我是用了当treap模板题做的。
解释一下变量吧......s(x,0)表示左儿子，s(x,1)表示右儿子，siz是子树的大小,w是当前点的权值,pos是随机出来的一个值，用于保证treap的尽量平衡。
有人说我缩行严重QAQ......?我明明没有一行超过了80行被D线的......而且同一行的语句从逻辑上来说是有关联的啊......?
treap的旋转操作：
```cpp
void up(int i){siz[i]=siz[s[i][0]]+siz[s[i][1]]+1;}
void spin(int &i,int p){
int t=s[i][p];
s[i][p]=s[t][!p],s[t][!p]=i,up(i),up(t),i=t;
}
```
那么讲讲treap做法：
1.插入：给每个点随机一个优先级，然后如果子节点的优先级要小于父节点，我们就把子节点旋转上去。
```cpp
void ins(int x,int &i){
if(!i){i=++tot,siz[i]=1,w[i]=x,pos[i]=rand();return;}
siz[i]++;
if(x<=w[i]){ins(x,s[i][0]);if(pos[s[i][0]]<pos[i])spin(i,0);}
else {ins(x,s[i][1]);if(pos[s[i][1]]<pos[i])spin(i,1);}
}
```
2.删除：将这个点优先级小的子节点旋转上来，一直将其旋到叶子，然后删除。
```cpp
void del(int x,int &i){
if(w[i]==x){
if(s[i][0]*s[i][1]==0){i=s[i][0]+s[i][1];return;}
if(pos[s[i][0]]>pos[s[i][1]]){spin(i,1);del(x,s[i][0]);}
else {spin(i,0);del(x,s[i][1]);}
}
else if(w[i]>x)del(x,s[i][0]);
else del(x,s[i][1]);
up(i);
}
```
3.查找x数的排名
只要维护左右子树的大小就可以了，但是要注意一点：因为我们查询的是最小的排名，所以当我们查到x数的时候，不应该之间返回，而应该递归下去，直到到达0为止（开始就是因为这个才WA的，也注意不要写如果其左儿子还是x就继续递归否则返回，因为可能还有x在其左儿子的右子树中。）
```cpp
int find(int x,int i){
if(!i)return 1;
if(w[i]>=x)return find(x,s[i][0]);
return find(x,s[i][1])+siz[s[i][0]]+1;
}
```
4.查找排名为x的数
这个就更简单了不是吗？
```cpp
int ask(int x,int i){
if(siz[s[i][0]]==x-1)return w[i];
if(siz[s[i][0]]>=x)return ask(x,s[i][0]);
return ask(x-siz[s[i][0]]-1,s[i][1]);
}
```
5/6：查找前驱/后继
前驱：找到一个比x小的数，就记录这个数并判断这个数的右子树（比这个数大的数）中是否还有比x小的数。如果没找到，就往左子树中继续找。
后继同理。
```cpp
int pre(int x,int i){
if(!i)return -2000000005;
if(w[i]<x)return max(w[i],pre(x,s[i][1]));
else return pre(x,s[i][0]);
}
int nxt(int x,int i){
if(!i)return 2000000005;
if(w[i]>x)return min(w[i],nxt(x,s[i][0]));
else return nxt(x,s[i][1]);
}
```