题解 P3369 【【模板】普通平衡树(Treap/SBT)】
「QQ红包」
2017-07-27 22:01:04
正常的treap解法
前驱和后继就二分
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
node* ch[2];
int w;
int v;
int s;//节点数
int flag;//由于某种原因,所以~
node()
{
ch[0]=NULL;
ch[1]=NULL;
w=rand();
v=0;
s=1;
flag=1;
}
};
node* root;
inline void maintain(node* &u)//更新该节点所对的树的节点总数
{
u->s=u->flag;//flag存的是权值为v的点的个数
if (u->ch[0]!=NULL) u->s+=u->ch[0]->s;//左子树不为空就加上左子树的节点数
if (u->ch[1]!=NULL) u->s+=u->ch[1]->s;//右子树不为空就加上右子树的节点数
}
inline void turn(node* &u,int d)//左旋右旋,d=0:左旋,1:右旋
{//我们假设为左旋
node* k=u->ch[d^1];//提出u的右子树,u的右子数的根节点作为整个树的根节点
u->ch[d^1]=k->ch[d];//右子树的左节点,作根节点的右节点
k->ch[d]=u;//原本的树u,作k树的左子树
maintain(u);//更新u之后k才能更新
maintain(k);//更新k
u=k;//赋过去
}
inline void insert(node* &u,int d)
{
if (u==NULL)//如果u为空直接插进去
{
u=new node;
u->v=d;
return;
} else
if (u->v==d)//因为可能有相同的,所以统flag,然后更新
{
u->flag++;
maintain(u);
return;
}
int d1=d>u->v?1:0;//判断是应该搜左子树还是右子树
insert(u->ch[d1],d);
if (u->ch[d1]->w > u->w) turn(u,d1^1); //看搜的子树的权重,比较,旋转
else maintain(u); //旋转过程中已经更了节点数,没旋也要更新
}
inline void remove(node* &u,int d)
{
if (u==NULL) return;//空的就退掉
if (u->v==d)
{
if (u->flag>1) u->flag--;//如果这个值出现多次直接减
else
{
if (u->ch[0]==NULL&&u->ch[1]==NULL)
{//没左子树和右子树直接删除
u=NULL;
} else
if (u->ch[0]!=NULL&&u->ch[1]!=NULL)
{//有两个子树就看哪边权重大,然后旋过去,然后继续搜那个子树
if (u->ch[0]->w >u->ch[1]->w) turn (u,1),remove(u->ch[1],d); else turn(u,0),remove(u->ch[0],d);
} else
{//只有一个子树就直接拿另一个棵子树补上
if (u->ch[0]==NULL) u=u->ch[1]; else u=u->ch[0];
}
}
if (u!=NULL) maintain(u);//不为空才统计
} else
{//根据d的大小扫左子树和右子树
if (d < u->v) remove(u->ch[0],d); else
if (d > u->v) remove(u->ch[1],d);
if (u!=NULL) maintain(u);//更新
}
}
inline int sum(node* u,int k)//查询排名为k的数
{
if (k<0||k>u->s||u==NULL) return 0; //不合法的情况直接退出
int ss=0;//ss:u的左子树的节点个数,没有则为0,省得分类讨论
if (u->ch[0]!=NULL) ss=u->ch[0]->s;//更新
if (k>=ss+1&&k<=u->flag+ss) return u->v;//嗯因为u有flag个,所以在ss+1~ss+flag这个范围就算找到了
if (ss>=k) return sum(u->ch[0],k); //ss大了就往左子树扫
else return sum(u->ch[1],k-ss-u->flag);//否则就搜右子树
}
inline int ans(node* u,int k)//查询k的排名
{
if (u==NULL) return 0;//不合法的情况
int ss=0;//存左子树的节点数,不然没左子树就要再分
if (u->ch[0]!=NULL) ss=u->ch[0]->s;
if (u->v==k) return ss+1;//返回排名最小的,所以是ss+1
if (u->v>k) //大了搜左边
{
return ans(u->ch[0],k);
}
else//搜右子输的时候要把左子树的节点数加上
{
return ss+u->flag+ans(u->ch[1],k);
}
}
inline void qq(node* u,int k,int &ans)//求k的前驱
{
if (u==NULL) return;
if (u->v<k)
{
if (u->v > ans) ans=u->v;//日常更新,没有往左扫的必要了
if (u->ch[1]!=NULL) qq(u->ch[1],k,ans);//所以右子树不为空就扫
} else
if (u->v>=k)//大了的话就往左扫,仅此而已
{
if (u->ch[0]!=NULL) qq(u->ch[0],k,ans);
} //左子树不为空就往左扫
}
inline void hj(node* u,int k,int &ans)//求k的后继
{
if (u==NULL) return;
if (u->v>k)//其实原理和前驱差不多
{
if (u->v < ans) ans=u->v;//更新
if (u->ch[0]!=NULL) hj(u->ch[0],k,ans);//扫左子树看有更接近的没
} else
if (u->v<=k)
{
if (u->ch[1]!=NULL) hj(u->ch[1],k,ans);//扫右子树
}
}
int T,a,b;
int main()
{
srand(937);
scanf("%d",&T);
while (T--)//6种操作
{
scanf("%d%d",&a,&b);
if (a==1)
{
insert(root,b);
} else
if (a==2)
{
remove(root,b);
} else
if (a==3)
{
int ans3=ans(root,b);
printf("%d\n",ans3);
} else
if (a==4)
{
int ans4=sum(root,b);
printf("%d\n",ans4);
} else
if (a==5)
{
int ans5=0;
qq(root,b,ans5);
printf("%d\n",ans5);
} else
if (a==6)
{
int ans6=100000000;//毫无意义的初值
hj(root,b,ans6);
printf("%d\n",ans6);
}
}
return 0;
}
```