普通平衡树（指针splay）

最早的板子，学自Ez大佬：

  1 #include<cstdio>
  2 #include<cstdlib>
  3 using namespace std;
  4  
  5 class Splay{
  6 public:
  7     Splay(){
  8         root=NULL;
  9         for(top;top<siez;top++)
 10             stk[top]=tree+top;
 11     }
 12     inline void insert(int val){
 13         if(find(val)!=NULL)
 14             ++root->cnt,update(root);
 15         else    if(root==NULL)
 16             root=newnode(val,NULL);
 17         else    splay(insert(root,val),NULL);
 18     }
 19     inline void erase(int val){
 20         if(find(val)!=NULL) erase(root,1);
 21     }
 22     inline int rnk(int val){
 23         if(find(val)!=NULL) return size(root->son[0])+1;
 24         else    return 0;
 25     }
 26     inline int qry(int kth){
 27         if(size(root)<kth)  return 0;
 28         for(node *t=root;t;){
 29             if(kth>size(t->son[0])){
 30                 kth-=size(t->son[0]);
 31                 if(kth<=t->cnt)
 32                     return t->v;
 33                 else    kth-=t->cnt,t=t->son[1];
 34             }
 35             else    t=t->son[0];
 36         }
 37     }
 38     inline int prv(int val){
 39         int ret=-0x7fffffff;
 40         for(node *t=root;t;){
 41             if(t->v<val){
 42                 if(ret<t->v)
 43                     ret=t->v;
 44             }
 45             t=t->son[val>t->v];
 46         }
 47         return ret;
 48     }
 49     inline int nxt(int val){
 50         int ret=0x7fffffff;
 51         for(node *t=root;t;){
 52             if(t->v>val){
 53                 if(ret>t->v)
 54                     ret=t->v;
 55             }
 56             t=t->son[val>=t->v];
 57         }
 58         return ret;
 59     }
 60 private:
 61     struct node{
 62         int v,cnt,siz;
 63         node *son[2],*f;
 64         node(){son[0]=son[1]=f=NULL;v=cnt=siz=0;}
 65     }*root;
 66     const static int siez=100100;
 67     node *stk[siez],tree[siez];int top;
 68     inline node * newnode(int v,node *f){
 69         node *t=stk[--top];
 70         t->siz=t->cnt=1;t->v=v;
 71         t->son[1]=t->son[0]=NULL;
 72         t->f=f;
 73         return t;
 74     }
 75     inline void freenode(node *t){
 76         stk[top++]=t;
 77     }
 78     inline int size(node* t){
 79         return t==NULL?0:t->siz;
 80     }
 81     inline void update(node *t){
 82         if(t!=NULL)
 83             t->siz=t->cnt+size(t->son[0])+size(t->son[1]);
 84     }
 85     
 86     inline bool son(node* f,node* s){
 87         if(f==NULL) return 0;
 88         return f->son[1]==s;
 89     }
 90     inline void connect(node *f,node *s,bool k){
 91         if(f!=NULL) f->son[k]=s;
 92         else    root=s;
 93         if(s!=NULL) s->f=f;
 94     }
 95     inline void rotate(node* t){
 96         node *f=t->f,*g=f->f;
 97         bool a=son(f,t),b=!a;
 98         connect(f,t->son[b],a);
 99         connect(g,t,son(g,f));
100         connect(t,f,b);
101         update(f);
102         update(t);
103     }
104     inline  void splay(node *t,node *p){
105         if(t){
106             while(t->f!=p){
107                 node *f =t->f,*g=f->f;
108                 if(g==p)    rotate(t);
109                 else{
110                     if(son(g,f)^son(f,t))
111                         rotate(t),rotate(t);
112                     else
113                         rotate(f),rotate(t);
114                 }
115             }
116         }
117     }
118     inline node *find(int val){
119         node *t=root;
120         while(t!=NULL &&t->v!=val){
121             t=t->son[val>=t->v];
122         }
123         return splay(t,NULL ),t;
124     }
125     node *insert(node *t,int val){
126         node *ret=t->son[val>=t->v];
127         if(ret==NULL)
128             ret=t->son[val>=t->v]=newnode(val,t);
129         else ret=insert(ret,val);
130         return update(t),ret;
131     }
132     inline void erase(node *t){
133         if(t->son[0]==NULL)
134             connect(NULL ,t->son[1],0),update(root);
135         else    if(t->son[1]==NULL){
136             connect(NULL,t->son[0],1),update(root);
137         }
138         else{
139             node *p=t->son[0];
140             while(p->son[1]!=NULL)  p=p->son[1];
141             splay(p,t);
142             connect(NULL,p,0);
143             connect(p,t->son[1],1);
144             update(root);
145         }
146         freenode(t);
147     }
148     inline void erase(node *t ,int k){
149         t->cnt-=k;
150         if(t->cnt<=0)   erase(t);
151         else    update(t);
152     }
153 }s;
154 int main(){
155     freopen("phs.in","r",stdin);
156     freopen("phs.out","w",stdout);
157     int n,op,x;
158     scanf("%d",&n);
159     while(n--){
160         scanf("%d%d",&op,&x);
161         switch(op){
162             case 1: s.insert(x);
163             break;
164             case 2 :s.erase(x);
165             break;
166             case 3: printf("%d
",s.rnk(x));
167             break;
168             case 4:printf("%d
",s.qry(x));
169             break;
170             case 5:printf("%d
",s.prv(x));
171             break;
172             default:printf("%d
",s.nxt(x));
173             break;
174         }
175     }
176 }

The old

自己修改的板子（其实没变化）：

  1 #define Troy
  2 
  3 #include "bits/stdc++.h"
  4 
  5 #define inf 0x7fffffff
  6 
  7 using namespace std;
  8 
  9 inline int read(){
 10     int s=0,k=1;char ch=getchar();
 11     while(ch<'0'|ch>'9')    ch=='-'?k=-1:0,ch=getchar();
 12     while(ch>47&ch<='9')    s=s*10+(ch^48),ch=getchar();
 13     return s*k;
 14 }
 15 
 16 const int N=2e5+5;
 17 
 18 #define size(t) (t?t->size:0)
 19 #define son(f,s)    (f?f->son[1]==s:0)
 20 #define update(t)    (t?t->size=t->cnt+size(t->son[0])+size(t->son[1]):0)
 21 
 22 class Splay{
 23 public:
 24     Splay(){for(root=NULL;top<N;++top)   stk[top]=tree+top;}
 25     
 26     inline void insert(int val){
 27         if(find(val)) ++root->cnt,update(root);
 28         else    if(root)    splay(insert(root,val),NULL);
 29         else    root=newnode(val,NULL);
 30     }
 31 
 32     inline void erase(int val){if(find(val))   erase(root,1);}
 33 
 34     inline int rnk(int val){
 35         if(find(val))   return size(root->son[0])+1;
 36         else    return 0;
 37     }
 38 
 39     inline int qry(int kth){
 40         if(size(root)<kth)  return 0;
 41         for(node *t=root;t;)
 42             if(kth>size(t->son[0])){
 43                 kth-=size(t->son[0])+t->cnt;
 44                 if(kth<=0)  return t->val;
 45                 else    t=t->son[1];
 46             }else t=t->son[0];
 47     }   
 48 
 49     inline int prv(int val){
 50         int ret=-inf;
 51         for(node *t=root;t;t=t->son[val>t->val])
 52             if(t->val<val&&ret<t->val)  ret=t->val;
 53         return ret;  
 54     }
 55 
 56     inline int nxt(int val){
 57         int ret=inf;
 58         for(node *t=root;t;t=t->son[val>=t->val])
 59             if(t->val>val&&ret>t->val)  ret=t->val;
 60         return ret;
 61     }
 62 private:
 63     struct node{
 64         node *f,*son[2];
 65         int val,cnt,size;
 66     }tree[N],*root,*stk[N];int top;
 67 
 68     inline node* newnode(int val,node *f){
 69         node *t=stk[--top];*t=(node){f,NULL,NULL,val,1,1};
 70         return t;
 71     }
 72 
 73     inline void freenode(node *t){stk[top++]=t;}
 74 
 75     inline void connect(node *f,node *s,int k){
 76         if(f)   f->son[k]=s;else root=s;
 77         if(s)   s->f=f;
 78     }
 79 
 80     inline void rotate(node *t){
 81         node *f=t->f,*g=f->f;int a=son(f,t),b=!a;
 82         connect(f,t->son[b],a);
 83         connect(g,t,son(g,f));
 84         connect(t,f,b);
 85         update(f),update(t);
 86     }
 87 
 88     inline void splay(node *t,node *p){
 89         if(t)for(;t->f!=p;rotate(t))
 90             if(t->f->f!=p)  rotate(son(t->f,t)==son(t->f->f,t->f)?t->f:t);
 91     }
 92 
 93     inline node *find(int val){
 94         node *t=root;
 95         for(;t&&t->val!=val;t=t->son[val>=t->val]);
 96         return splay(t,NULL),t;
 97     }
 98 
 99     inline node *insert(node *t,int val){
100         node *ret=t->son[val>=t->val];
101         if(ret) ret=insert(ret,val);else    ret=t->son[val>=t->val]=newnode(val,t);
102         return update(t),ret;
103     }
104 
105     inline void erase(node *t){
106         if(t->son[0]==NULL) connect(NULL,t->son[1],0);
107         else    if(t->son[1]==NULL) connect(NULL,t->son[0],0);
108         else    {node *p=t->son[0];
109             while(p->son[1])    p=p->son[1];
110             splay(p,t);
111             connect(NULL,p,0),connect(p,t->son[1],1);
112         }update(root),freenode(t);
113     }
114 
115     inline void erase(node *t,int k){
116         t->cnt-=k;
117         if(t->cnt<=0)   erase(t);else   update(t);
118     }
119 }s;
120 int main(){
121     freopen("phs.in","r",stdin);
122     freopen("phs.out","w",stdout);
123     int n,op,x;
124     n=read();
125     while(n--){
126         op=read(),x=read();
127         switch(op){
128             case 1: s.insert(x);
129             break;
130             case 2 :s.erase(x);
131             break;
132             case 3:printf("%d
",s.rnk(x));
133             break;
134             case 4:printf("%d
",s.qry(x));
135             break;
136             case 5:printf("%d
",s.prv(x));
137             break;
138             default:printf("%d
",s.nxt(x));
139             break;
140         }
141     }
142 }