平衡树

#include<bits/stdc++.h>
using namespace std;

namespace ftp {
    const int MAXN=(int)1e6+10;
    struct Node {
        int value,random,size,lson,rson;
    } tree[MAXN];
    #define val(p) tree[p].value
    #define rnd(p) tree[p].random
    #define siz(p) tree[p].size
    #define l(p) tree[p].lson
    #define r(p) tree[p].rson

    int cnt=0,root=0,x=0,y=0,z=0;

    void update(int p)
    {
        siz(p)=siz(l(p))+siz(r(p))+1;
    }

    void split(int p,int k,int &x,int &y)
    {
        if (p==0) {
            x=y=0;
            return;
        }
        if (val(p)<=k) {
            x=p;
            split(r(p),k,r(p),y);
        } else {
            y=p;
            split(l(p),k,x,l(p));
        }
        update(p);
    }

    int merge(int x,int y)
    {
        if (x==0 || y==0) {
            return x+y;
        }
        if (rnd(x)<rnd(y)) {
            r(x)=merge(r(x),y);
            update(x);
            return x;
        } else {
            l(y)=merge(x,l(y));
            update(y);
            return y;
        }
    }

    inline int rand()
    {
        static int seed=19260817;
        return seed=seed*23333LL%0x7fffffff;
    }

    int newNode(int v)
    {
        tree[++cnt]={v,rand(),1,0,0};
        return cnt;
    }

    void ins(int v)
    {
        split(root,v,x,y);
        root=merge(merge(x,newNode(v)),y);
    }

    void del(int v)
    {
        split(root,v,x,z);
        split(x,v-1,x,y);
        y=merge(l(y),r(y));
        root=merge(merge(x,y),z);
    }

    int rnk(int v)
    {
        split(root,v-1,x,y);
        int ans=siz(x)+1;
        root=merge(x,y);
        return ans;
    }

    int kth(int p,int k)
    {
        while (true) {
            if (k<=siz(l(p))) {
                p=l(p);
            } else if (k==siz(l(p))+1) {
                return val(p);
            } else {
                k-=siz(l(p))+1;
                p=r(p);
            }
        }
    }

    int pre(int v)
    {
        split(root,v-1,x,y);
        int ans=kth(x,siz(x));
        root=merge(x,y);
        return ans;
    }

    int suf(int v)
    {
        split(root,v,x,y);
        int ans=kth(y,1);
        root=merge(x,y);
        return ans;
    }
}

int main()
{
    int n;
    cin>>n;
    for (int i=0;i<n;i++) {
        int opt,v;
        scanf("%d%d",&opt,&v);
        switch (opt) {
            case 1:
                ftp::ins(v);
                break;
            case 2:
                ftp::del(v);
                break;
            case 3:
                printf("%d\n",ftp::rnk(v));
                break;
            case 4:
                printf("%d\n",ftp::kth(ftp::root,v));
                break;
            case 5:
                printf("%d\n",ftp::pre(v));
                break;
            case 6:
                printf("%d\n",ftp::suf(v));
                break;
        }
    }
    return 0;
}