1 /**************************************************************  2     Problem: 3224  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:212 ms  7     Memory:4032 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <cstdlib> 12 #include <ctime> 13   14 #define lson tr[r].l 15 #define rson tr[r].r 16 using namespace std; 17 const int N = 100001; 18 const int Maxlen = 900005; 19   20 struct treap_node { 21     int l, r, v, sz, key, cnt; 22 }tr[N]; 23   24 int n, cnt, root, ans, x; 25 char buf[Maxlen]; 26 int Left, Len; 27   28 inline int read() { 29     int x = 0, sgn = 1; 30     while (buf[Left] < ‘0‘ || ‘9‘ < buf[Left]) 31         if (buf[Left++] == ‘-‘) sgn = -1; 32     while (‘0‘ <= buf[Left] && buf[Left] <= ‘9‘) 33         x = x * 10 + buf[Left++] - ‘0‘; 34     return sgn * x; 35 } 36    37 int len = 0, pr[15]; 38 inline void print(int x) { 39     if (x < 0) putchar(‘-‘), x = -x; 40     while (x) 41         pr[++len] = x % 10, x /= 10; 42     if (!len) putchar(‘0‘); 43     while (len) 44         putchar(pr[len--] + ‘0‘); 45     puts(""); 46 } 47   48   49 inline void update(int r) { 50     tr[r].sz = tr[lson].sz + tr[rson].sz + tr[r].cnt; 51 } 52   53 inline void rturn(int &r) { 54     int t = lson; 55     lson = tr[t].r; 56     tr[t].r = r, tr[t].sz = tr[r].sz; 57     update(r); 58     r = t; 59 } 60   61 inline void lturn(int &r) { 62     int t = rson; 63     rson = tr[t].l; 64     tr[t].l = r, tr[t].sz = tr[r].sz; 65     update(r); 66     r = t; 67 } 68   69 void ins(int &r) { 70     if (r == 0) { 71         r = ++cnt; 72         tr[r].sz = tr[r].cnt = 1; 73         tr[r].v = x; 74         tr[r].key = rand(); 75         return; 76     } 77     ++tr[r].sz; 78     if (tr[r].v == x) 79         ++tr[r].cnt; 80     else if (x > tr[r].v) { 81         ins(rson); 82         if (tr[rson].key < tr[r].key) 83             lturn(r); 84     } else { 85         ins(lson); 86         if (tr[lson].key < tr[r].key) 87             rturn(r); 88     } 89 } 90   91 void del(int &r) { 92     if (r == 0) return; 93     if (tr[r].v == x) { 94         if (tr[r].cnt > 1) { 95             --tr[r].cnt, --tr[r].sz; 96             return; 97         } 98         if (!lson || !rson) 99             r = lson + rson;100         else if (tr[lson].key < tr[rson].key)101                 rturn(r), del(r);102         else lturn(r), del(r);              103     }104     else if (x > tr[r].v) --tr[r].sz, del(rson);105     else --tr[r].sz, del(lson);106 }107  108 int query_rank(int r) {109     if (r == 0) return 0;110     if (tr[r].v == x) 111         return tr[lson].sz + 1;112     else if (x > tr[r].v) 113         return tr[lson].sz + tr[r].cnt + query_rank(rson);114     return query_rank(lson);115 }116  117 int query_kth (int r, int x) {118     if (r == 0) return 0;119     if (x <= tr[lson].sz) return query_kth(lson, x);120     else if (x > tr[lson].sz + tr[r].cnt)121         return query_kth(rson, x - tr[lson].sz - tr[r].cnt);122     else return tr[r].v;123 }124  125 void query_pre(int r) {126     if (r == 0) return;127     if (tr[r].v < x) {128         ans = r;129         query_pre(rson);130     } else query_pre(lson);131 }132  133 void query_next(int r) {134     if (r == 0) return;135     if (tr[r].v > x) {136         ans = r;137         query_next(lson);138     } else query_next(rson);139 }140  141 int main() {142     int i, oper;143     Len = fread(buf, 1, Maxlen, stdin);144     buf[Len] = ‘ ‘;145     n = read();146     for (i = 1; i <= n; ++i) {147         oper = read(), x = read();148         if (oper == 1)149             ins(root); else150         if (oper == 2)151             del(root); else152         if (oper == 3)153             print(query_rank(root)); else154         if (oper == 4)155             print(query_kth(root, x)); else156         if (oper == 5) {157             ans = 0, query_pre(root);158             print(tr[ans].v);159         } else160         if (oper == 6) {161             ans = 0, query_next(root);162             print(tr[ans].v);163         }164     }165     return 0;166 }