image.png

    1. #include <bits/stdc++.h>
    3. #define int long long
    5. using namespace std;
    7. const int N = 1e6+5, INF = 1e9;
    9. int n, tot, rt;
    10. int tr[N][2];
    11. int val[N], dat[N];
    12. int size[N], cnt[N];
    14. int New(int v) {
    15.     val[++tot] = v;
    16.     dat[tot] = rand();
    17.     size[tot] = 1;
    18.     cnt[tot] = 1;
    19.     return tot;
    20. }
    22. void pushup(int u) {
    23.     size[u] = size[tr[u][0]]+size[tr[u][1]]+cnt[u];
    24. }
    26. void build() {
    27.     rt = New(-INF);
    28.     tr[rt][1] = New(INF);
    29.     pushup(rt);
    30. }
    32. void rotate(int &u, int d) {
    33.     int t = tr[u][d^1];
    34.     tr[u][d^1] = tr[t][d];
    35.     tr[t][d] = u;
    36.     u = t;
    37.     pushup(tr[u][d]);
    38.     pushup(u);
    39. } 
    41. void insert(int &u, int v) {
    42.     if (!u) {
    43.         u = New(v);
    44.         return ;
    45.     }
    46.     if (v == val[u]) {
    47.         cnt[u]++;
    48.     } else {
    49.         int d = v<val[u]?0:1;
    50.         insert(tr[u][d], v);
    51.         if (dat[u] < dat[tr[u][d]]) 
    52.             rotate(u, d^1);
    53.     }
    54.     pushup(u);
    55. } 
    57. void remove(int &u, int v) {
    58.     if (!u) 
    59.         return ;
    60.     if (v == val[u]) {
    61.         if (cnt[u] > 1) {
    62.             cnt[u]--;
    63.             pushup(u);
    64.             return ; 
    65.         }
    66.         if (tr[u][0] || tr[u][1]) {
    67.             if (!tr[u][1] || dat[tr[u][0]]>dat[tr[u][1]]) {
    68.                 rotate(u, 1);
    69.                 remove(tr[u][1], v);    
    70.             } else {
    71.                 rotate(u, 0);
    72.                 remove(tr[u][0], v);    
    73.             }
    74.             pushup(u);
    75.         } else {
    76.             u = 0;
    77.         }
    78.         return ;
    79.     }
    80.     if (v < val[u]) {
    81.         remove(tr[u][0], v);
    82.     } else {
    83.         remove(tr[u][1], v);
    84.     }
    85.     pushup(u);
    86. }
    88. int get_rank(int u, int v) {
    89.     if (!u) 
    90.         return -2;
    91.     if (v == val[u]) {
    92.         return size[tr[u][0]]+1;
    93.     } else if (v < val[u]) {
    94.         return get_rank(tr[u][0], v);
    95.     } else {
    96.         return size[tr[u][0]]+cnt[u]+get_rank(tr[u][1], v);
    97.     }
    98. }
    100. int get_val(int u, int rank) {
    101.     if (!u) 
    102.         return INF;
    103.     if (rank <= size[tr[u][0]]) {
    104.         return get_val(tr[u][0], rank);
    105.     } else if (rank <= size[tr[u][0]]+cnt[u]) {
    106.         return val[u];
    107.     } else {
    108.         return get_val(tr[u][1], rank-size[tr[u][0]]-cnt[u]);
    109.     }
    110. }
    112. int get_pre(int v) {
    113.     int u = rt, pre;
    114.     while (u) {
    115.         if (val[u] < v) {
    116.             pre = val[u];
    117.             u = tr[u][1];
    118.         } else {
    119.             u = tr[u][0];
    120.         }
    121.     }
    122.     return pre;
    123. }
    125. int get_next(int v) {
    126.     int u = rt, next;
    127.     while (u) {
    128.         if (val[u] > v) {
    129.             next = val[u];
    130.             u = tr[u][0];
    131.         } else {
    132.             u = tr[u][1];
    133.         }
    134.     }
    135.     return next;
    136. }
    138. signed main() {
    139.     build();
    140.     cin >> n;
    141.     for (int i = 1; i <= n; i++) {
    142.         int op, x;
    143.         scanf("%lld%lld", &op, &x);
    144.         if (op == 1) {
    145.             insert(rt, x);
    146.         } else if (op == 2) {
    147.             remove(rt, x);
    148.         } else if (op == 3) {
    149.             cout << get_rank(rt, x)-1 << "\n";
    150.         } else if (op == 4) {
    151.             cout << get_val(rt, x+1) << "\n";
    152.         } else if (op == 5) {
    153.             cout << get_pre(x) << "\n";
    154.         } else if (op == 6) {
    155.             cout << get_next(x) << "\n";
    156.         }
    157.     }
    158.     return 0;
    159. }