SPLAY

#include
    
     #include
     
      #include
      
       #define N 1000005using namespace std;int ch[N][2],f[N],size[N],cnt[N],key[N],root,sz;inline void clear(int x){  ch[x][0]=ch[x][1]=f[x]=size[x]=cnt[x]=key[x]=0;}inline bool get(int x){  return ch[f[x]][1]==x;}inline void update(int x){    if(x){      size[x]=cnt[x];      if(ch[x][0]) size[x]+=size[ch[x][0]];      if(ch[x][1]) size[x]+=size[ch[x][1]];    }}inline void rotate(int x){    int p=f[x],g=f[p],wz=get(x);    ch[p][wz]=ch[x][wz^1];    if(ch[p][wz]) f[ch[p][wz]]=p;    ch[x][wz^1]=p;    f[p]=x; f[x]=g;    if(g) ch[g][ch[g][1]==p]=x;    update(p); update(x);}inline void splay(int x){       for(int fa;fa=f[x];rotate(x))         if(f[fa])           rotate((get(x)==get(fa))?fa:x);       root=x;}inline void insert(int x){    if(root==0){      sz++; ch[sz][0]=ch[sz][1]=f[sz]=0;      size[sz]=cnt[sz]=1; key[sz]=x; root=sz;      return ;    }    int now=root,fa=0;    while(1){      if(x==key[now]){        cnt[now]++;update(now); 		update(fa); splay(now);        break;      }      fa=now; now=ch[fa][key[fa]
       
        1){cnt[root]--; size[root]--; return;}    if(!ch[root][0]&&!ch[root][1]){clear(root); root=0; return ;}    if(!ch[root][0]){      int old=root; root=ch[root][1];      f[root]=0; clear(old);      return ;    }    if(!ch[root][1]){      int old=root; root=ch[root][0];      f[root]=0; clear(old);      return ;    }    int big=pre(),old=root; splay(big);    ch[root][1]=ch[old][1]; f[ch[root][1]]=root;    clear(old); update(root);}int main(){    int n,opt,x;    scanf("%d",&n);    while(n--)    {      scanf("%d%d",&opt,&x);      if(opt==1) insert(x);      if(opt==2) del(x);      if(opt==3) printf("%d\n",rank(x));      if(opt==4) printf("%d\n",find(x));      if(opt==5){        insert(x);         printf("%d\n",key[pre()]);        del(x);      }      if(opt==6){        insert(x);         printf("%d\n",key[next()]);        del(x);      }    }    return 0;}
       
      
     
    

啊啊啊，我以前打的好丑啊啊啊啊啊...........

TREAP

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define size(a) ((a!=NULL)?(a)->size:0)using namespace std;struct Node{ Node *ch[2]; int key,size,num,tot; Node(int x=0){ key=rand();num=x;size=tot=1; memset(ch,0,sizeof ch); } void* operator new (size_t); void operator delete (void *p);}*root,*C,*M; vector
           
             q; void* Node :: operator new (size_t){ if(C==M){ C=new Node[1<<15]; M=C+(1<<15); } return C++;}void Node :: operator delete (void *p){ q.push_back((Node*)p);}void pushup(Node *now){ if(!now) return; now->size=size(now->ch[0])+size(now->ch[1])+now->tot;}void rot(Node *&now,int wh){ Node *son=now->ch[wh]; now->ch[wh]=son->ch[wh^1]; pushup(now); son->ch[wh^1]=now; pushup(son); now=son;}void insert(Node *&now,int x){ if(!now){ now=new Node(x); return ; } if(now->num==x){now->size+=1;now->tot+=1;return;} int wh=now->num
            
             ch[wh],x); pushup(now); if(now->ch[wh]->key
             
              key) rot(now,wh);}void del(Node *&now,int x){ if(now->num==x){ if(now->tot>1){now->size-=1;now->tot-=1;return;} if(!now->ch[0]&&!now->ch[1]){delete now;now=NULL;} else if(!now->ch[0]){ Node *t=now; now=now->ch[1]; delete t; t=NULL; } else if(!now->ch[1]){ Node *t=now; now=now->ch[0]; delete t; t=NULL; } else{ int wh=now->ch[0]->key>now->ch[1]->key; rot(now,wh); del(now,x); } } else{ if(now->num>x)del(now->ch[0],x); else del(now->ch[1],x); } if(now) pushup(now);}int Rank(int x){ int ans=1; Node *now=root; while(now){ if(now->num
              
               ch[0])+now->tot; now=now->ch[1]; } else if(now->num==x){ans+=size(now->ch[0]);break;} else now=now->ch[0]; } return ans;}int kth(int x){ Node *now=root; int all=x; while(now){ if(size(now->ch[0])>=all) {now=now->ch[0];continue;} all-=size(now->ch[0]); if(now->tot>=all) return now->num; all-=now->tot; now=now->ch[1]; }}int pre(int x){return kth(Rank(x)-1);}int next(int x){return kth(Rank(x+1));}int main(){ int n,opt,x; srand(time(NULL)); scanf("%d",&n); while(n--) { scanf("%d%d",&opt,&x); switch(opt){ case 1: insert(root,x); break; case 2: del(root,x); break; case 3: printf("%d\n",Rank(x)); break; case 4: printf("%d\n",kth(x)); break; case 5: printf("%d\n",pre(x)); break; case 6: printf("%d\n",next(x)); break; } }}