思路：
劳资敲了一个多星期；
劳资终于a了；
劳资一直不a是因为一个小错误；
劳资最后看的模板；
劳资现在很愤怒；
劳资不想谈思路！！！
来，上代码：
#include <cstdio> using namespace std; #define maxn 1000005 struct SplayTreeNodeType { int w,key,opi,size,ch[2]; }; struct SplayTreeNodeType tree[maxn]; int n,root,tot; inline void updata(int now) { tree[now].size=tree[now].w; if(tree[now].ch[0]) tree[now].size+=tree[tree[now].ch[0]].size; if(tree[now].ch[1]) tree[now].size+=tree[tree[now].ch[1]].size; } inline int pre() { int now=tree[root].ch[0]; while(tree[now].ch[1]) now=tree[now].ch[1]; return now; } inline int suc() { int now=tree[root].ch[1]; while(tree[now].ch[0]) now=tree[now].ch[0]; return now; } inline int getson(int now) { return tree[tree[now].opi].ch[1]==now; } void rotate(int now) { int opi=tree[now].opi,fopi=tree[opi].opi,pos=getson(now); tree[opi].ch[pos]=tree[now].ch[pos^1]; tree[tree[opi].ch[pos]].opi=opi; tree[now].ch[pos^1]=opi;tree[opi].opi=now; tree[now].opi=fopi; if(fopi) tree[fopi].ch[tree[fopi].ch[1]==opi]=now; updata(opi),updata(now); } void splay(int now) { for(int opi;opi=tree[now].opi;rotate(now)) { if(tree[opi].opi) rotate(getson(now)==getson(opi)?opi:now); } root=now; } int rank(int x) { int now=root,ans=0; while(1) { if(x<tree[now].key) now=tree[now].ch[0]; else { ans+=tree[now].ch[0]?tree[tree[now].ch[0]].size:0; if(x==tree[now].key) { splay(now); return ans+1; } ans+=tree[now].w; now=tree[now].ch[1]; } } } int rank_(int x) { int now=root; while(1) { if(tree[now].ch[0]&&x<=tree[tree[now].ch[0]].size) now=tree[now].ch[0]; else { int tmp=(tree[now].ch[0]?tree[tree[now].ch[0]].size:0)+tree[now].w; if(x<=tmp) return tree[now].key; x-=tmp;now=tree[now].ch[1]; } } } inline void clear(int now) { tree[now].ch[0]=tree[now].ch[1]=tree[now].w=tree[now].size=tree[now].key=tree[now].opi=0; } inline void create(int x) { tree[++tot].key=x; tree[tot].w=tree[tot].size=1; tree[tot].ch[0]=tree[tot].ch[1]=tree[tot].opi=0; } void insert(int x) { if(!root) create(x),root=tot; else { int now=root,opi=0; while(1) { if(tree[now].key==x) { tree[now].w++; tree[now].size++; splay(now); break; } opi=now; now=tree[now].ch[x>tree[opi].key]; if(!now) { create(x); tree[tot].opi=opi; tree[opi].ch[x>tree[opi].key]=tot; splay(tot); break; } } } } void del(int x) { int t=rank(x); if(tree[root].w>1) { tree[root].w--; tree[root].size--; return ; } if(!tree[root].ch[0]&&!tree[root].ch[1]) { clear(root); root=0; return ; } if(!tree[root].ch[0]) { int tmp=root; root=tree[root].ch[1]; tree[root].opi=0; clear(tmp); return ; } if(!tree[root].ch[1]) { int tmp=root; root=tree[root].ch[0]; tree[root].opi=0; clear(tmp); return ; } int pre1=pre(),tmp=root; splay(pre1); tree[root].ch[1]=tree[tmp].ch[1]; tree[tree[tmp].ch[1]].opi=root; clear(tmp);updata(root); } inline void in(int &now) { register int if_z=1;now=0; register char Cget=getchar(); while(Cget>'9'||Cget<'0') { if(Cget=='-') if_z=-1; Cget=getchar(); } while(Cget>='0'&&Cget<='9') { now=now*10+Cget-'0'; Cget=getchar(); } now*=if_z; } int main() { in(n);int ty,x; while(n--) { in(ty),in(x); if(ty==1) insert(x); if(ty==2) del(x); if(ty==3) printf("%d ",rank(x)); if(ty==4) printf("%d ",rank_(x)); if(ty==5) insert(x),printf("%d ",tree[pre()].key),del(x); if(ty==6) insert(x),printf("%d ",tree[suc()].key),del(x); } return 0; }