一种很牛~的算法，超级烦琐 给我的感觉就是：背模板才是王道~ 所以下面就献上一道裸题，方便模板的练习
bzoj3224 Description
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作： 1. 插入x数 2. 删除x数(若有多个相同的数，因只删除一个) 3. 查询x数的排名(若有多个相同的数，因输出最小的排名) 4. 查询排名为x的数 5. 求x的前驱(前驱定义为小于x，且最大的数) 6. 求x的后继(后继定义为大于x，且最小的数)
Input
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)
Output
对于操作3,4,5,6每行输出一个数，表示对应答案
Sample Input
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
Sample Output
106465
84185
492737
这里写代码片 #include<cstdio> #include<cstring> #include<iostream> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; const int INF=1e9; const int MAX_Q = 1e5 + 10; int n,top=0; struct node{ int v,size,cnt; //cnt是避免这个位置上有多个相同权值的节点 node *ch[2],*pre; //前驱和儿子 void update() { size=ch[0]->size+ch[1]->size+cnt; } int get_wh() { return pre->ch[0]==this ? 0:1; //当前节点是爸爸的左儿子还是右儿子 } void set_ch(int wh,node *child); }pool[MAX_Q],*root,*null; void node::set_ch(int wh,node *child) //建儿子 *取地址符，变参 { ch[wh]=child; if (child!=null) child->pre=this; update(); } inline node *get_new(int v) { node *now=pool + ++top; //获取新结点的指针； now->size=1; now->v=v; now->cnt=1; now->pre=now->ch[0]=now->ch[1]=null; return now; } inline void rotate(node *&now) { node *old_father=now->pre; node *grand=now->pre->pre; int wh=now->get_wh(); old_father->set_ch(wh,now->ch[wh^1]); now->set_ch(wh^1,old_father); now->pre=grand; if (grand!=null) grand->ch[grand->ch[0]==old_father ? 0:1]=now; } inline void splay(node *now,node *tar) { for (;now->pre!=tar;rotate(now)) //每两次中都要转一次当前节点，所以直接把rotate(now)写在了循环里 if (now->pre->pre!=tar) //爸爸的爸爸不是目标，也就是至少还要旋转两次 now->pre->get_wh()==now->get_wh() ? rotate(now->pre):rotate(now); //爸爸和儿子的方向相同，转爸爸，否则转儿子 if (tar==null) root=now; } void insert(int v) //插入 { node *last=null; //从哪来的 node *now=root; node *newone=get_new(v); //获取新节点 while (now!=null) { last=now; if (now->v==newone->v) { now->size++; now->cnt++; splay(now,null); return; } else if (newone->v<now->v) //以权值为维护小根堆的标准 now=now->ch[0]; else now=now->ch[1]; } if (last==null) //树为空 root=newone; else { if (newone->v<last->v) last->set_ch(0,newone); else last->set_ch(1,newone); splay(newone,null); } return; } inline node *find(int v) { node *now=root; while (now!=null) { if (now->v==v) break; if (v<now->v) now=now->ch[0]; else now=now->ch[1]; } if (now!=null) splay(now,null); return now; } inline void del(int v) { node *now=find(v); if (now==null) return; if (now->cnt>1) { now->cnt--; now->size--; return; } if (now->ch[0]==null&&now->ch[1]==null) root=null; else if (now->ch[1]==null) { now->ch[0]->pre=null; root=now->ch[0]; } else if (now->ch[0]==null) { now->ch[1]->pre=null; root=now->ch[1]; } else { node *_=now->ch[0]; while (_->ch[1]!=null) _=_->ch[1]; splay(_,now); _->set_ch(1,now->ch[1]); _->pre=null; root=_; } return; } inline int pre(int v) { int ans=-INF; node *now=root; while (now!=null) { if (now->v<v) ans=max(ans,now->v),now=now->ch[1]; else now=now->ch[0]; } return ans; } inline int nxt(int v) { int ans=INF; node *now=root; while (now!=null) { if (now->v>v) ans=min(ans,now->v),now=now->ch[0]; else now=now->ch[1]; } return ans; } inline int get_rank(int v) { node *now=root; int left=0; while (now!=null) { if (now->v==v) { int ans=left+now->ch[0]->size+1; splay(now,null); return ans; } if (v<now->v) now=now->ch[0]; else left+=now->ch[0]->size+now->cnt,now=now->ch[1]; } return -1; } inline int kth(int k) { node *now=root; int left=0; while (now!=null) { int _=left+now->ch[0]->size; if (_+1<=k&&k<=_+now->cnt) { splay(now,null); return now->v; } if (k<=_) now=now->ch[0]; else left=_+now->cnt,now=now->ch[1]; //先前计算的_就已经累加了left，所以这里一定是"=" } return -1; } int main() { null=pool; null->v=0; null->size=0; null->cnt=0; null->pre=null->ch[0]=null->ch[1]=null; root=null; /* 1. 插入x数 2. 删除x数(若有多个相同的数，因只删除一个) 3. 查询x数的排名(若有多个相同的数，因输出最小的排名) 4. 查询排名为x的数 5. 求x的前驱(前驱定义为小于x，且最大的数) 6. 求x的后继(后继定义为大于x，且最小的数)*/ int q; scanf("%d",&q); while (q--) { int order,_; scanf("%d",&order); scanf("%d",&_); switch(order) { case 1: insert(_); break; case 2: del(_); break; case 3: printf("%d\n",get_rank(_)); break; case 4: printf("%d\n",kth(_)); break; case 5: printf("%d\n",pre(_)); break; case 6: printf("%d\n",nxt(_)); break; } } return 0; }