Tyvj 1728 普通平衡树
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)
Output对于操作3,4,5,6每行输出一个数，表示对应答案
Input
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
Output
106465
84185
492737
Hint
1.n的数据范围：n<=100000
2.每个数的数据范围：[-2e9,2e9]
sol：留了很久的巨坑终于尝试着来填了。
推荐一篇讲的很好blog但是代码不可看的教程(保证学会)
自己的模板，代码中有详细的注释，可配合上面的教程阅读，体验感极差
#include <bits/stdc++.h> using namespace std; typedef int ll; inline ll read() { ll s=0; bool f=0; char ch=' '; while(!isdigit(ch)) { f|=(ch=='-'); ch=getchar(); } while(isdigit(ch)) { s=(s<<3)+(s<<1)+(ch^48); ch=getchar(); } return (f)?(-s):(s); } #define R(x) x=read() inline void write(ll x) { if(x<0) { putchar('-'); x=-x; } if(x<10) { putchar(x+'0'); return; } write(x/10); putchar((x%10)+'0'); return; } #define W(x) write(x),putchar(' ') #define Wl(x) write(x),putchar(' ') const int N=200005,inf=0x3f3f3f3f; int n; namespace Pht { int Points; //总的节点数(重复元素算一个) int Root; //根节点 int Child[N][2]; //左右儿子 int Parent[N]; //父亲 int Cnt[N]; //这个节点的元素个数 int Quanzhi[N]; //这个点的权值 int Size[N]; //这棵字数的元素个数 inline void Init(); inline int Check(int x); inline void PushUp(int x); inline void Rotate(int x); inline void Splay(int x); inline void Insert(int x); inline void Remove(int x); inline void Find(int x); inline int Ask_Lower(int x); inline int Ask_Upper(int x); inline int Ask_Kth(int x); inline void Init() { Points=Root=0; Insert(inf); Insert(-inf); return; } inline int Check(int x)//查询这个节点是左右儿子 { return (Child[Parent[x]][0]==x)?0:1; } inline void PushUp(int x)//跟新子树中的元素个数 { Size[x]=Cnt[x]+Size[Child[x][0]]+Size[Child[x][1]]; return; } inline void Rotate(int x) { int y,z,oo; y=Parent[x]; z=Parent[y]; oo=Check(x); //查询x是左右儿子 Child[y][oo]=Child[x][oo^1]; Parent[Child[x][oo^1]]=y; //把x的另一个子树连给父亲 Child[z][Check(y)]=x; Parent[x]=z; //x连给爷爷 Child[x][oo^1]=y; Parent[y]=x; //父亲连给x PushUp(x); PushUp(y); //跟新子树元素个数 } inline void Splay(int At,int To)//把At转到To { while(Parent[At]!=To) { int Father=Parent[At]; if(Parent[Father]==To)//当前节点的爷爷已经是To了 { Rotate(At); } else if(Check(At)==Check(Father)) //在一条连线上时双旋 { Rotate(Father); Rotate(At); } else { Rotate(At); Rotate(At); //否则单旋*2 } } if(To==0) Root=At;//之前一直理解不了(我也不知道为什么),TMD转到0节点下面了当然就是根了啊 } inline void Insert(int Val) //插入权值为Val的节点 { int Now=Root,Par=0; while(Now&&Quanzhi[Now]!=Val) { Par=Now; Now=Child[Now][(Val>Quanzhi[Now])?1:0]; } if(Now) //已经有这个权值了 { Cnt[Now]++; Size[Now]++; } else //没有这个权值就新建一个节点 { Now=++Points; if(Par) { Child[Par][(Val>Quanzhi[Par])?1:0]=Now; } Child[Now][0]=Child[Now][1]=0; Parent[Now]=Par; Quanzhi[Now]=Val; Cnt[Now]=Size[Now]=1; } Splay(Now,0); //每次插入都要转到根,可以防止被卡T return; } inline void Remove(int Val) //删除权值为Val的节点 { int Lower=Ask_Lower(Val),Upper=Ask_Upper(Val); Splay(Lower,0); Splay(Upper,Lower); int Pos=Child[Upper][0];//Lower比Val小,所以Lower转上去后Val是Lower的右二子,再把Upper转到Lower上,Val肯定就是Upper的左儿子了 if(Cnt[Pos]>1) { Cnt[Pos]--; //有多个数字 Splay(Pos,0); } else Child[Upper][0]=0; } inline void Find(int Val) //寻找权值为Val的节点的位置 { int Now=Root; if(!Root) return;//不能找 while(Child[Now][(Val>Quanzhi[Now])?1:0]&&(Val!=Quanzhi[Now]))//找权值Val的位置 { Now=Child[Now][(Val>Quanzhi[Now])?1:0]; } Splay(Now,0); } inline int Ask_Lower(int Val)//查询权值为Val的节点的前驱 { Find(Val); int Now=Root; if(Quanzhi[Now]<Val) return Now; Now=Child[Now][0]; while(Child[Now][1]) Now=Child[Now][1]; return Now; } inline int Ask_Upper(int Val)//查询权值为Val的节点的后继 { Find(Val); int Now=Root; if(Quanzhi[Now]>Val) return Now; Now=Child[Now][1]; while(Child[Now][0]) Now=Child[Now][0]; return Now; } inline int Ask_Kth(int Id)//查询第k大的数 { int Now=Root; if(Size[Now]<Id) return 0; for(;;)//查询第k大的数,挺像主席树的 { if(Id>Size[Child[Now][0]]+Cnt[Now]) { Id-=Size[Child[Now][0]]+Cnt[Now]; Now=Child[Now][1]; } else if(Size[Child[Now][0]]>=Id) Now=Child[Now][0]; else return Quanzhi[Now]; } } } int main() { R(n); Pht::Init(); while(n--) { int opt=read(),x=read(); switch (opt) { case 1: Pht::Insert(x); break; case 2: Pht::Remove(x); break; case 3: Pht::Find(x); Wl(Pht::Size[Pht::Child[Pht::Root][0]]+1-1);//加1是因为之前的都是比x小的,所以加1,但是一开始插入了一个-inf所以-1 break; case 4: x++;//一开始有一个-inf Wl(Pht::Ask_Kth(x)); break; case 5: Wl(Pht::Quanzhi[Pht::Ask_Lower(x)]); break; case 6: Wl(Pht::Quanzhi[Pht::Ask_Upper(x)]); break; } } return 0; } /* input 10 1 106465 4 1 1 317721 1 460929 1 644985 1 84185 1 89851 6 81968 1 492737 5 493598 output 106465 84185 492737 */