这道题就是裸的平衡树的题目，操作都是模板，也就不多说了，重在代码。

SBT:

#include
     
      struct SBT {    int v, sz, ch[2], cnt;} t[300005];int n, cnt, root;#define Upd(k) {\    t[k].sz = t[t[k].ch[0]].sz + t[t[k].ch[1]].sz + t[k].cnt;\}void rot(int &k, bool f) {    int p = t[k].ch[f]; t[k].ch[f] = t[p].ch[!f]; t[p].ch[!f] = k;    Upd(k); Upd(p); k = p;}inline void mt(int &k,bool f){    if(!k) return;    if(t[t[k].ch[f^1]].sz < t[t[t[k].ch[f]].ch[f]].sz) rot(k, f);    else if(t[t[k].ch[f^1]].sz < t[t[t[k].ch[f]].ch[f^1]].sz) { rot(t[k].ch[f], f^1); rot(k, f); }    else return;    mt(t[k].ch[f],f);    mt(k,f);}void Ins(int &k, int x) {    if(!k) {k = ++ cnt; t[k].sz = t[k].cnt = 1; t[k].v = x; return; }    ++ t[k].sz;    if(t[k].v == x) {++ t[k].cnt; return;}    Ins(t[k].ch[t[k].v < x], x);    mt(k, t[k].v < x);}int Del(int &k, int x) {    if(!k) return k;    int tmp;    if(t[k].v == x) {        if(t[k].cnt > 1) {-- t[k].cnt; --t[k].sz; return k;}        else if(!(t[k].ch[0]*t[k].ch[1])) {k = t[k].ch[0]+t[k].ch[1];}        else { tmp = Del(t[k].ch[0], x+1); t[k].cnt = t[tmp].cnt; t[k].v = t[tmp].v; Upd(k); return k; }    }    else if((t[k].v < x && !t[k].ch[1]) || (t[k].v > x && ! t[k].ch[0])) { tmp = k; k = t[k].ch[0]; Upd(k); return tmp; }    else tmp = Del(t[k].ch[t[k].v < x], x);    Upd(k); return tmp;}int Ran(int k,int x) {    if(k==0)return 0;    if(t[k].v==x)return t[t[k].ch[0]].sz+1;    else if(x>t[k].v)        return t[t[k].ch[0]].sz+t[k].cnt+Ran(t[k].ch[1],x);    else return Ran(t[k].ch[0],x);}int Kth(int k,int x) {    if(k==0)return 0;    if(x<=t[t[k].ch[0]].sz)        return Kth(t[k].ch[0],x);    else if(x>t[t[k].ch[0]].sz+t[k].cnt)        return Kth(t[k].ch[1],x-t[t[k].ch[0]].sz-t[k].cnt);    else return t[k].v;}int ans;void pred(int k,int x) {    if(k==0)return;    if(t[k].v
      
       x) {        ans=k;        succ(t[k].ch[0],x);    } else succ(t[k].ch[1],x);}char c, f;inline void GET(int &n) {    n = 0; f = 1;    do {c = getchar(); if(c == '-') f = -1;} while(c > '9' || c < '0');    while(c >= '0' && c <= '9') {n=n*10+c-'0';c=getchar();}    n *= f;}int main() {    GET(n);    int opt,x;    for(int i=1; i<=n; i++) {        GET(opt); GET(x);        switch(opt) {            case 1: Ins(root,x); break;            case 2: Del(root,x); break;            case 3: printf("%d\n",Ran(root,x)); break;            case 4: printf("%d\n",Kth(root,x)); break;            case 5: ans=0; pred(root,x); printf("%d\n",t[ans].v); break;            case 6: ans=0; succ(root,x); printf("%d\n",t[ans].v); break;        }    }    return 0;}
      
     

Treap:

#include
     
      #include
      
       #include
       
        using namespace std;struct data {    int ch[2], v, sz, rnd, cnt;} tr[300005];int n,size,root,ans,sd = 2333;inline int ran() { return sd = (sd*sd+sd)%(10003); }inline void Upd(int k) {    tr[k].sz = tr[tr[k].ch[0]].sz + tr[tr[k].ch[1]].sz + tr[k].cnt;}void rot(int &k, bool f) { ///0->right_rotate    int t = tr[k].ch[f]; tr[k].ch[f] = tr[t].ch[!f]; tr[t].ch[!f] = k;    Upd(k); Upd(t); k = t;}void insert(int &k,int x) {    if(k==0) { size++; k=size; tr[k].sz=tr[k].cnt=1; tr[k].v=x; tr[k].rnd=ran(); return; }    tr[k].sz++;    if(tr[k].v==x) { tr[k].cnt++; return; }    bool f = x>tr[k].v;    insert(tr[k].ch[f],x);    if(tr[tr[k].ch[f]].rnd
        
         1) { tr[k].cnt--; tr[k].sz--; return; }        if(tr[k].ch[0]*tr[k].ch[1]==0)k=tr[k].ch[0]+tr[k].ch[1];        else rot(k, tr[tr[k].ch[0]].rnd >= tr[tr[k].ch[1]].rnd), del(k, x);    } else tr[k].sz--, del(tr[k].ch[x>tr[k].v], x);}int get_rank(int k,int x) {    if(k==0)return 0;    if(tr[k].v==x)return tr[tr[k].ch[0]].sz+1;    else if(x>tr[k].v)        return tr[tr[k].ch[0]].sz+tr[k].cnt+get_rank(tr[k].ch[1],x);    else return get_rank(tr[k].ch[0],x);}int get_kth(int k,int x) {    if(k==0)return 0;    if(x<=tr[tr[k].ch[0]].sz)        return get_kth(tr[k].ch[0],x);    else if(x>tr[tr[k].ch[0]].sz+tr[k].cnt)        return get_kth(tr[k].ch[1],x-tr[tr[k].ch[0]].sz-tr[k].cnt);    else return tr[k].v;}void pred(int k,int x) {    if(k==0)return;    if(tr[k].v
         
          x) {        ans=k;        succ(tr[k].ch[0],x);    } else succ(tr[k].ch[1],x);}char c, f;inline void GET(int &n) {    n = 0; f = 1;    do {c = getchar(); if(c == '-') f = -1;} while(c > '9' || c < '0');    while(c >= '0' && c <= '9') {n=n*10+c-'0';c=getchar();}    n *= f;}int main() {    GET(n);    int opt,x;    for(int i=1; i<=n; i++) {        GET(opt); GET(x);        switch(opt) {            case 1: insert(root,x); break;            case 2: del(root,x); break;            case 3: printf("%d\n",get_rank(root,x)); break;            case 4: printf("%d\n",get_kth(root,x)); break;            case 5: ans=0; pred(root,x); printf("%d\n",tr[ans].v); break;            case 6: ans=0; succ(root,x); printf("%d\n",tr[ans].v); break;        }    }    return 0;}
         
        
       
      
     

Splay

#include
     
      #define MAXN 300005struct node {    int v, cnt, sz, ch[2], f;}t[MAXN];int rt, sz, n;#define Upd(r) {t[r].sz = t[t[r].ch[0]].sz + t[t[r].ch[1]].sz + t[r].cnt;}void rot(int x){    int y = t[x].f, z = t[y].f;    bool f = (t[y].ch[1] == x);    t[y].ch[f] = t[x].ch[f^1];    if(t[y].ch[f]) t[t[y].ch[f]].f = y;    t[x].ch[f^1] = y; t[y].f = x;    t[x].f = z;    if(z) t[z].ch[t[z].ch[1]==y] = x;    Upd(y);}void Spaly(int r, int tp) {    for(int y, z; (y = t[r].f) != tp; rot(r)) {        z = t[y].f;        if(z == tp) continue;        if( (t[z].ch[0] == y) == (t[y].ch[0] == r) ) rot(y);        else rot(r);    }    if(!tp) rt = r; Upd(r);}void Ins(int r, int x) {    int y = 0;    while(r && t[r].v != x) { y = r; r = t[r].ch[x > t[r].v]; }    if(r) ++ t[r].cnt;    else {        r = ++ sz; t[r].sz = t[r].cnt = 1;        t[r].v = x; t[r].f = y; if(y) t[y].ch[x > t[y].v] = r;    }    Spaly(r, 0);}void Find(int v) {    int x = rt; if(!x) return;    while(t[x].ch[v > t[x].v] && t[x].v != v) x = t[x].ch[v > t[x].v];    Spaly(x, 0);}int Ran(int v) {    Find(v);    return t[t[rt].ch[0]].sz;}int Kth(int x){    int y=rt,p;    if(x>t[rt].sz)return 0;    while(1)    {        p=t[y].ch[0];        if(t[p].sz+t[y].cnt
      
       =x) y=p;        else return t[y].v;    }}int Nxt(int x, bool f){    Find(x);    if((t[rt].v>x&&f)||(t[rt].v
       
         1) -- t[p].cnt, Spaly(p, 0);    else t[s].ch[0] = 0;}char c, f;inline void GET(int &n) {    n = 0; f = 1;    do {c = getchar(); if(c == '-') f = -1;} while(c > '9' || c < '0');    while(c >= '0' && c <= '9') {n=n*10+c-'0';c=getchar();}    n *= f;}int main() {    GET(n);    int opt,x;    Ins(rt, -0x7fffffff); Ins(rt, +0x7fffffff);    for(int i=1; i<=n; i++) {        GET(opt); GET(x);        switch(opt) {            case 1: Ins(rt,x); break;            case 2: Del(x); break;            case 3: printf("%d\n",Ran(x)); break;            case 4: printf("%d\n",Kth(x+1)); break;            case 5: printf("%d\n",t[Nxt(x, 0)].v); break;            case 6: printf("%d\n",t[Nxt(x, 1)].v); break;        }    }    return 0;}