Title Description

You need to write a data structure (refer to the title of the title) to maintain some numbers. The following operations are required:

Insert xx number
Delete xx number (if there are more than one same number, only one will be deleted)
Query the ranking of xx numbers (the ranking is defined as the number of numbers smaller than the current number + 1 + 1). If there are more than one identical number, the lowest ranking will be output.)
Number of queries ranked xx
Find the antecedent of xx (the definition of antecedent is less than xx, and the maximum number)
Find the successor of xx (the successor is defined as the minimum number greater than xx)
I / O format

Input format:
The first line is nn, indicating the number of operations. The next nn line has two numbers, optop and xx. Optop indicates the sequence number of operations (1 \leq opt \leq 6 1 ≤ opt ≤ 6)

Output format:
For operation 3,4,5,63,4,5,6, output one number per line, indicating the corresponding answer

Example of input and output

Input sample (1): copy
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
Output sample 1: copy
106465
84185
492737
Explain

Space time limit: 1000ms,128M

Data range of 1.n: n \leq 100000 n ≤ 100000

2. Data range of each number: [- {10} ^ 7, {10} ^ 7] [- 10
7
,10
7
]

Source: Tyvj1728 original name: ordinary balance tree

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
const int MAXN = 100005;
const int inf = 0x7f7f7f7f;

struct Node{
    int v,fa;
    int ch[2];
    int sum;
    int recy;
}node[MAXN];


int n,cnt,points;

inline void update(int x){
    node[x].sum=node[node[x].ch[1]].sum+node[node[x].ch[0]].sum+node[x].recy;   
}

inline bool jud(int x){
    return node[node[x].fa].ch[0]==x?0:1;
}

inline void connect(int x,int f,int son){
    node[x].fa=f;
    node[f].ch[son]=x;
}

inline void rotate(int x){
    int y=node[x].fa;
    int mroot=node[y].fa;
    int mrootson=jud(y);
    int yson=jud(x);
    int oth=node[x].ch[yson^1];
    connect(oth,y,yson);
    connect(y,x,(yson^1));
    connect(x,mroot,mrootson);
    update(y);update(x);
}

inline void splay(int at,int to){
    to=node[to].fa;
    while(node[at].fa!=to){
        int up=node[at].fa;
        if(node[up].fa==to) rotate(at);
        else if(jud(up)==jud(at)){
            rotate(up);
            rotate(at);
        }
        else{
            rotate(at);
            rotate(at);
        }
    }
}

inline int crepoint(int x,int f){
    node[++cnt].v=x;
    node[cnt].fa=f;
    node[cnt].sum=1;
    node[cnt].recy=1;
    return cnt;
}

inline void destroy(int x){
    node[x].v=node[x].fa=node[x].sum=node[x].recy=node[x].ch[0]=node[x].ch[1]=0;
    if(x==cnt) cnt--;
}

inline int find(int v){
    int now=node[0].ch[1];
    while(1){
        if(node[now].v==v){
            splay(now,node[0].ch[1]);
            return now;
        }
        int nxt=v<node[now].v?0:1;
        if(!node[now].ch[nxt]) return 0;
        now=node[now].ch[nxt];
    } 
}

inline int build(int x){
    points++;
    if(cnt==0){
        node[0].ch[1]=1;
        crepoint(x,0);
    }
    else{
        int now=node[0].ch[1];
        while(1){
            node[now].sum++;
            if(x==node[now].v){
                node[now].recy++;
                return now;
            }
            int nxt=x<node[now].v?0:1;
            if(!node[now].ch[nxt]){
                crepoint(x,now);
                node[now].ch[nxt]=cnt;
                return cnt;
            }
            now=node[now].ch[nxt];
        }
    }
    return 0;
}

inline void push(int x){
    int add=build(x);
    splay(add,node[0].ch[1]);
}

inline void pop(int v){
    int deal=find(v);
    if(!deal) return;
    points--;
    if(node[deal].recy>1){
        node[deal].recy--;
        node[deal].sum--;
        return;
    }
    if(!node[deal].ch[0]){
        node[0].ch[1]=node[deal].ch[1];
        node[node[0].ch[1]].fa=0;
    }
    else{
        int lef=node[deal].ch[0];
        while(node[lef].ch[1]) lef=node[lef].ch[1];
        splay(lef,node[deal].ch[0]);
        int rig=node[deal].ch[1];
        connect(rig,lef,1);connect(lef,0,1);
        update(lef); 
    }
    destroy(deal);
}

int rank(int x){
    int ans=0;
    int now=node[0].ch[1];
    while(1){
        if(node[now].v==x) return ans+node[node[now].ch[0]].sum+1;
        if(now==0) return 0;
        if(x<node[now].v) now=node[now].ch[0];
        else{
            ans+=node[node[now].ch[0]].sum+node[now].recy;
            now=node[now].ch[1];
        }
    }
    if(now) splay(now,node[0].ch[1]);
    return 0;
}

int atrank(int x){
    if(x>points)    return -inf;
    int now=node[0].ch[1];
    while(1){
        int minn=node[now].sum-node[node[now].ch[1]].sum;
        if(x>node[node[now].ch[0]].sum && x<=minn) break;
        if(x<minn) now=node[now].ch[0];
        else{
            x=x-minn;
            now=node[now].ch[1];
        }
    }
    splay(now,node[0].ch[1]);
    return node[now].v;
}

inline int lower(int x){
    int now=node[0].ch[1];
    int res=-inf;
    while(now){
        if(node[now].v<x && node[now].v>res) res=node[now].v;
        if(x>node[now].v) now=node[now].ch[1];
        else now=node[now].ch[0];
    }
    return res;
}

inline int upper(int x){
    int now=node[0].ch[1];
    int res=inf;
    while(now){
        if(node[now].v>x && node[now].v<res) res=node[now].v;
        if(x<node[now].v) now=node[now].ch[0];
        else now=node[now].ch[1];
    }
    return res;
}

int main(){
    scanf("%d",&n);
    push(inf);push(-inf);
    for(register int i=1;i<=n;i++){
        int opt,x;
        scanf("%d%d",&opt,&x);
        if(opt==1) push(x);
        else if(opt==2) pop(x);
        else if(opt==3) printf("%d\n",rank(x)-1);
        else if(opt==4) printf("%d\n",atrank(x+1));
        else if(opt==5) printf("%d\n",lower(x));
        else printf("%d\n",upper(x));
    }
    return 0;
}