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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
| namespace Treap{
#define ull unsigned long long
int n,m,q,rt,tot,a,b;
struct Node{
int son[2],val,cnt,data,siz;
}node[MAXN];
inline int Rand(){
static ull r=2333;
return (r*=233333LL)%=2147483647;
}
inline void push(int x){
node[x].siz = node[node[x].son[0]].siz+node[node[x].son[1]].siz+node[x].cnt;
}
inline int Build(int val){
node[++tot].val = val;
node[tot].cnt = 1;
node[tot].data = Rand();
node[tot].siz = 1;
return tot;
}
inline void Rotate(int &x, int d){
int k = node[x].son[d^1];
node[x].son[d^1] = node[k].son[d];
node[k].son[d] = x;
x = k;
push(node[x].son[d]);
push(x);
}
inline void Insert(int &x, int val){
if (!x) {x = Build(val);return;}
if (node[x].val==val) node[x].cnt++;
else if (node[x].val>val){
Insert(node[x].son[0],val);
if (node[x].data<node[node[x].son[0]].data) Rotate(x,1);
}else{
Insert(node[x].son[1],val);
if (node[x].data<node[node[x].son[1]].data) Rotate(x,0);
}
push(x);
}
inline void Delete(int &x, int val){
if (!x) return;
if (node[x].val==val){
if (node[x].cnt>1) {node[x].cnt--; push(x); return;}
if (node[x].son[0] || node[x].son[1]){
if (!node[x].son[1] || node[node[x].son[0]].data>node[node[x].son[1]].data) {
Rotate(x,1);
Delete(node[x].son[1],val);
}else{
Rotate(x,0);
Delete(node[x].son[0],val);
}
}
else x = 0;
}else if (node[x].val<val) Delete(node[x].son[1],val);
else Delete(node[x].son[0],val);
push(x);
}
inline int get_rnk(int val){
int x = rt,rnk = 0;
while(x){
if (node[x].val==val) return node[node[x].son[0]].siz+rnk+1;
if (node[x].val>val) x = node[x].son[0];
else rnk+=node[node[x].son[0]].siz+node[x].cnt,x=node[x].son[1];
}
return rnk;
}
inline int get_num(int rnk){
int x = rt;
while(x){
if (node[node[x].son[0]].siz+node[x].cnt>=rnk && node[node[x].son[0]].siz<rnk) return node[x].val;
if (node[node[x].son[0]].siz+node[x].cnt>=rnk){
x = node[x].son[0];
}else{
rnk-=node[node[x].son[0]].siz+node[x].cnt;
x = node[x].son[1];
}
}
return node[x].val;
}
inline int get_pre(int val){
int x = rt,pre = 0;
while(x){
if (node[x].val<val) pre = node[x].val, x = node[x].son[1];
else x = node[x].son[0];
}
return pre;
}
inline int get_nxt(int val){
int x = rt,nxt = 0;
while(x){
if (node[x].val>val) nxt = node[x].val, x = node[x].son[0];
else x = node[x].son[1];
}
return nxt;
}
inline void init(){
rt=Build(-2e9),node[rt].son[1]=Build(2e9),push(rt);
}
inline void solve();
#undef ull
}
|
