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
| #include <bits/stdc++.h>
struct Node {
Node *lc, *rc;
int num;
} *root[10010], memoryPool[11000010];
int cnt, a[10010], n, m;
inline void insert(Node *&p, int l, int r, int value) {
if (p == NULL) p = &memoryPool[cnt++];
if (l == r) {
p->num++;
return;
}
register int mid = l + r >> 1;
if (value <= mid) insert(p -> lc, l, mid, value);
else insert(p->rc, mid + 1, r, value);
p->num = 0;
if (p->lc) p->num += p->lc->num;
if (p->rc) p->num += p->rc->num;
}
inline void erase(Node *&p, int l, int r, int value) {
if (p == NULL) p = &memoryPool[cnt++];
if (l == r) {
p->num--;
return;
}
register int mid = l + r >> 1;
if (value <= mid) erase(p->lc, l, mid, value);
else erase(p->rc, mid + 1, r, value);
p->num = 0;
if (p->lc) p->num += p->lc->num;
if (p->rc) p->num += p->rc->num;
}
inline int query(Node *&p, int l, int r, int value) {
if (!p) return 0;
if (l == r) return p -> num;
register int mid = l + r >> 1, ret = 0;
if (value <= mid) ret += query(p->lc, l, mid, value);
else {
if (p->lc) ret += p->lc->num;
ret += query(p->rc, mid + 1, r, value);
}
return ret;
}
inline void insert(int x, int y) { for (; x <= n; x += (x & -x)) insert(root[x], 0, 1000000000, y); }
inline void erase(int x, int y) { for (; x <= n; x += (x & -x)) erase(root[x], 0, 1000000000, y); }
inline int query(int x, int y) {
int ret = 0;
for (; x > 0; x -= (x & -x)) ret += query(root[x], 0, 1000000000, y);
return ret;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++) scanf("%d", &a[i]), insert(i, a[i]);
char str[2];
for (register int i = 1, x, y, z; i <= m; i ++) {
scanf("%s", str), scanf("%d%d", &x, &y);
if (str[0] == 'Q') {
scanf("%d", &z);
register int l = 0, r = 1000000000;
while (l < r) {
register int mid = (l + r) / 2;
if (query(y, mid) - query(x - 1, mid) >= z) r = mid;
else l = mid + 1;
}
std::cout << l << "\n";
}
else {
erase(x, a[x]), a[x] = y, insert(x, a[x]);
}
}
return 0;
}
|
