题解 P6136 【【模板】普通平衡树（数据加强版）】
BFqwq
·
·
题解
WBLT
由于考虑到等会有又是一堆 splay，treap，顾先为 WBLT 党占个坑。
WBLT 是一种 leafy tree。所谓 leafy tree，就是指所有的信息放在叶节点上，然后内部节点维护叶节点的合并信息。
这好像很像我们熟悉的线段树，因此，线段树就是一类 leafy tree。
因此 WBLT 的查询操作与线段树十分相似，需要走到叶节点才能完成查询。
先看看变量
const int ratio=4;
struct lef{
int v,w,ls,rs;
}t[maxn*80];
int rt,tot,ans,lastans;
void nnd(int &o,int v,int w,int ls,int rs){
o=++tot;
t[o]=(lef){v,w,ls,rs};
}
这个因数在修改中有用。
$v$ 是指这棵子树内最大的树的值。
$w$ 是指这棵子树的重量，也就是**叶**节点数量。注意**不**包括内部节点的数量。
$ls,rs$ 为左右儿子。
#### 查询操作
查询操作和线段树的写法没有什么区别。
```
int qrk(int o,int k) {
if(t[o].w==1) return 1;
if(k<=t[t[o].ls].v)return qrk(t[o].ls,k);
else return t[t[o].ls].w+qrk(t[o].rs,k);
}
int qnm(int o,int k) {
if(t[o].w==1) return t[o].v;
if(k<=t[t[o].ls].w)return qnm(t[o].ls,k);
else return qnm(t[o].rs,k-t[t[o].ls].w);
}
int pre(int rk,int x){
return qnm(rt,qrk(rt,x)-1);
}
int suf(int rk,int x){
return qnm(rt,qrk(rt,x+1));
}
```
对于查排名，只要不断比较该值与左边节点的 $v$ 值大小，确定进入左子树还是右子树。
查询 $kth$ 则不断比较与该节点左边节点的 $w$ 大小。
#### 调整操作
当左右节点的 $w$ 相差过大时（一般认定是一边大于另一边的 $ratio$ 倍）我们就需要做出调整。
调整的方式如下：如果右子树过大，则将左子树和右子树的左子树合并成一棵子树，右子树的右子树独立作一颗子树。
具体一点，是建立一个新节点作为当前节点的左儿子，新节点的左儿子是原来的 $ls$，新节点的右儿子是原来右儿子的 $ls$。
原来右儿子的 $rs$ 做当前节点的 $rs$。
左子树过大同理。
```cpp
void merge(int &o,int x,int y){
nnd(o,t[y].v,t[x].w+t[y].w,x,y);
}
void maintain(int o){
if(t[t[o].ls].w>t[t[o].rs].w*ratio){
merge(t[o].rs,t[t[o].ls].rs,t[o].rs);
t[o].ls=t[t[o].ls].ls;
}
if(t[t[o].rs].w>t[t[o].ls].w*ratio){
merge(t[o].ls,t[o].ls,t[t[o].rs].ls);
t[o].rs=t[t[o].rs].rs;
}
}
```
由于我们是从下往上层层调整的，因此不用担心左儿子的右儿子过大这种事。
可以说，这一步保证了树的复杂度。
#### 插入操作
我们找到比这个数小的最大叶节点（或是大的最小叶节点），然后将这个叶节点分裂。
具体的方法为这个叶节点新建两个子节点，分别记录原来的数和新数。
然后原节点就作一个内部节点。
在修改的时候一路往上调整。
```cpp
void pushup(int o){
if(!t[o].ls){
t[o].w=1;
return;
}
t[o].w=t[t[o].ls].w+t[t[o].rs].w;
t[o].v=t[t[o].rs].v;
}
void ins(int o,int x){
if(t[o].w==1){
nnd(t[o].ls,min(t[o].v,x),1,0,0);
nnd(t[o].rs,max(t[o].v,x),1,0,0);
}
else{
ins(x>t[t[o].ls].v?t[o].rs:t[o].ls,x);
}
pushup(o);maintain(o);
}
```
#### 删除操作
先找到要删掉的叶节点，然后判断。
如果这个叶节点的父节点没有另一个子节点，则直接删掉。
如果有另一个子节点，则让另一个子节点上位代替父节点的位置。
同样，一路调整。
```
void del(int o,int x){
int wh,el;
if(x<=t[t[o].ls].v) wh=t[o].ls,el=t[o].rs;
else wh=t[o].rs,el=t[o].ls;
if(t[wh].w==1)
if(x==t[wh].v){
t[o].ls=t[el].ls;
t[o].rs=t[el].rs;
t[o].v=t[el].v;
}
else return;
else del(wh,x);
pushup(o);maintain(o);
}
```
#### 初始化
一开始要先建立一个根节点。一般来说，根节点的值选择 $inf$。（因为一开始根节点也是叶节点）
#### 代码
```
#include <bits/stdc++.h>
using namespace std;
inline int read(){
register int x=0;
register bool f=0;
register char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+c-48;
c=getchar();
}
return f?-x:x;
}
char cr[200];int tt;
inline void print(int x,char k='\n') {
if(!x) putchar('0');
if(x < 0) putchar('-'),x=-x;
while(x) cr[++tt]=x%10+'0',x/=10;
while(tt) putchar(cr[tt--]);
putchar(k);
}
const int maxn=100010;
const int ratio=4;
struct lef{
int v,w,ls,rs;
}t[maxn*80];
int rt,tot,ans,lastans;
void nnd(int &o,int v,int w,int ls,int rs){
o=++tot;
t[o]=(lef){v,w,ls,rs};
}
void merge(int &o,int x,int y){
nnd(o,t[y].v,t[x].w+t[y].w,x,y);
}
void pushup(int o){
if(!t[o].ls){
t[o].w=1;
return;
}
t[o].w=t[t[o].ls].w+t[t[o].rs].w;
t[o].v=t[t[o].rs].v;
}
void maintain(int o){
if(t[t[o].ls].w>t[t[o].rs].w*ratio){
merge(t[o].rs,t[t[o].ls].rs,t[o].rs);
t[o].ls=t[t[o].ls].ls;
}
if(t[t[o].rs].w>t[t[o].ls].w*ratio){
merge(t[o].ls,t[o].ls,t[t[o].rs].ls);
t[o].rs=t[t[o].rs].rs;
}
}
int qrk(int o,int k) {
if(t[o].w==1) return 1;
if(k<=t[t[o].ls].v)return qrk(t[o].ls,k);
else return t[t[o].ls].w+qrk(t[o].rs,k);
}
int qnm(int o,int k) {
if(t[o].w==1) return t[o].v;
if(k<=t[t[o].ls].w)return qnm(t[o].ls,k);
else return qnm(t[o].rs,k-t[t[o].ls].w);
}
void ins(int o,int x){
if(t[o].w==1){
nnd(t[o].ls,min(t[o].v,x),1,0,0);
nnd(t[o].rs,max(t[o].v,x),1,0,0);
}
else{
ins(x>t[t[o].ls].v?t[o].rs:t[o].ls,x);
}
pushup(o);maintain(o);
}
void del(int o,int x){
int wh,el;
if(x<=t[t[o].ls].v) wh=t[o].ls,el=t[o].rs;
else wh=t[o].rs,el=t[o].ls;
if(t[wh].w==1)
if(x==t[wh].v){
t[o].ls=t[el].ls;
t[o].rs=t[el].rs;
t[o].v=t[el].v;
}
else return;
else del(wh,x);
pushup(o);maintain(o);
}
int pre(int rk,int x){
return qnm(rt,qrk(rt,x)-1);
}
int suf(int rk,int x){
return qnm(rt,qrk(rt,x+1));
}
signed main(){
int n=read(),m=read();
nnd(rt,2147483647,1,0,0);
for(int i=1;i<=n;i++){
int a=read();ins(rt,a);
}
while(m--){
int opt=read(),x=read()^lastans;
switch(opt){
case 1:ins(rt,x);break;
case 2:del(rt,x);break;
case 3:lastans=qrk(rt,x);break;
case 4:lastans=qnm(rt,x);break;
case 5:lastans=pre(rt,x);break;
case 6:lastans=suf(rt,x);break;
}
if(opt!=1&&opt!=2) ans^=lastans;
}
print(ans);
return 0;
}
```