1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int CN = 1e5+5;
int read(){
int s = 0,ne = 1; char c = getchar();
for(;c < '0' || c > '9';c = getchar()) if(c == '-') ne = -1;
for(;c >= '0' && c <= '9';c = getchar()) s = (s << 1) + (s << 3) + c - '0';
return s * ne;
}
class Splay{
public: int ch[CN][2],fa[CN],val[CN],sz[CN],cnt[CN],tot,rt;
Splay() {memset(ch, 0, sizeof(ch)); memset(fa, 0, sizeof(fa)); tot = rt = 0;}
#define lc ch[u][0]
#define rc ch[u][1]
bool get(int u) {return u == ch[ fa[u] ][1];}
void maintain(int u) {sz[u] = sz[lc] + sz[rc] + cnt[u];}
void clear(int u) {lc = rc = sz[u] = val[u] = fa[u] = cnt[u] = 0;}
void make(int f,int k) {int u = ++tot; sz[u] = cnt[u] = 1, val[u] = k, fa[u] = f; if(f) ch[f][val[f] < k] = u;}
void rotate(int u){
int f = fa[u], gf = fa[ fa[u] ], chk = get(u);
ch[f][chk] = ch[u][chk ^ 1], fa[ ch[u][chk ^ 1] ] = f;
ch[u][chk ^ 1] = f, fa[f] = u;
fa[u] = gf; if(gf) ch[gf][f == ch[gf][1]] = u;
maintain(f), maintain(u);
}
void splay(int u){
for(int f = fa[u]; f = fa[u]; rotate(u)) if(fa[f]) rotate(get(f) == get(u) ? f : u);
rt = u;
}
void _ins(int u,int f,int k){
if(!u) {make(f, k); rt = tot; maintain(f); return;}
if(val[u] == k) {cnt[rt = u]++,sz[u]++; maintain(f); return;}
_ins(val[u] > k ? lc : rc, u, k);
}
void ins(int k) {_ins(rt, 0, k); splay(rt);}
int _rank(int u,int k) {return val[u] == k ? rt = u, sz[lc] + 1 : (val[u] > k ? _rank(lc, k) : sz[lc] + cnt[u] + _rank(rc, k));}
int rank(int k) {int r = _rank(rt, k); splay(rt); return r;}
int _kth(int u,int k) {return sz[lc] >= k ? _kth(lc, k) : (sz[lc] + cnt[u] >= k ? val[rt = u] : _kth(rc, k - sz[lc] - cnt[u]));}
int kth(int k) {int r = _kth(rt, k); splay(rt); return r;}
int pre() {int u = ch[rt][0]; while(rc) u = rc; return u;}
int nxt() {int u = ch[rt][1]; while(lc) u = lc; return u;}
void del(int k){
rank(k); int u = rt;
if(cnt[u] > 1) {sz[u]--,cnt[u]--; return;}
if(!lc && !rc) {rt = 0, clear(u); return;}
if(!lc) {rt = rc, fa[rc] = 0; clear(u); return;}
if(!rc) {rt = lc, fa[lc] = 0; clear(u); return;}
int x = pre(); splay(x);
ch[x][1] = rc,fa[rc] = x; clear(u); maintain(x);
}
}t;
int n;
int main(){
n = read();
while(n--){
int tp = read(),x = read();
if(tp == 1) t.ins(x);
if(tp == 2) t.del(x);
if(tp == 3) printf("%d", t.rank(x));
if(tp == 4) printf("%d", t.kth(x));
if(tp == 5) t.ins(x), printf("%d", t.val[ t.pre() ]), t.del(x);
if(tp == 6) t.ins(x), printf("%d", t.val[ t.nxt() ]), t.del(x);
if(tp > 2) puts("");
}
}
|
