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

正常的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; } ```