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
| #include <bits/stdc++.h>
using namespace std;
#define id(x) (lower_bound(b + 1, b + L + 1, x) - b)
#define rid(x) (b[x])
#define lowbit(x) (x & (-x))
const int MAXN = 100005 * 2;
struct op {
char opt;
int i, j, k, t;
}ops[MAXN];
struct Node {
int l, r, sum;
Node() {l = r = sum = 0;}
}node[MAXN * 80];
int cnt, c[MAXN];
int N, M, L;
int a[MAXN], b[MAXN];
int qr[MAXN], ql[MAXN], qrlen, qllen;
void insert(int& u, int l, int r, int p, int val) {
if (u == 0) u = ++cnt;
node[u].sum += val;
if (l == r) return;
int mid = (l + r) >> 1;
if (p <= mid) insert(node[u].l, l, mid, p, val);
else insert(node[u].r, mid + 1, r, p, val);
}
void modify(int u, int p, int val) {
for (; u <= N; u += lowbit(u)) insert(c[u], 1, L, p, val);
}
void pre(int u, int* a, int& len) {
len = 0;
for (; u >= 1; u -= lowbit(u)) a[++len] = c[u];
}
int query(int l, int r, int k) {
if (l == r) return l;
int mid = (l + r) >> 1, lsum = 0;
for (int i = 1; i <= qrlen; ++i) lsum += node[node[qr[i]].l].sum;
for (int i = 1; i <= qllen; ++i) lsum -= node[node[ql[i]].l].sum;
if (lsum >= k) {
for (int i = 1; i <= qrlen; ++i) qr[i] = node[qr[i]].l;
for (int i = 1; i <= qllen; ++i) ql[i] = node[ql[i]].l;
return query(l, mid, k);
}
else {
for (int i = 1; i <= qrlen; ++i) qr[i] = node[qr[i]].r;
for (int i = 1; i <= qllen; ++i) ql[i] = node[ql[i]].r;
return query(mid + 1, r, k - lsum);
}
}
int main() {
scanf("%d%d", &N, &M);
for (register int i = 1; i <= N; ++i) {
scanf("%d", &a[i]), b[++L] = a[i], c[i] = ++cnt;
}
for (register int i = 1; i <= M; ++i) {
cin >> ops[i].opt;
if (ops[i].opt == 'Q') {
scanf("%d%d%d", &ops[i].i, &ops[i].j, &ops[i].k);
}
else {
scanf("%d%d", &ops[i].i, &ops[i].t);
b[++L] = ops[i].t;
}
}
sort(b + 1, b + L + 1);
L = unique(b + 1, b + L + 1) - b - 1;
for (register int i = 1; i <= N; ++i) {
a[i] = id(a[i]);
modify(i, a[i], 1);
}
for (register int i = 1; i <= M; ++i) {
if (ops[i].opt == 'Q') {
pre(ops[i].j, qr, qrlen);
pre(ops[i].i - 1, ql, qllen);
printf("%d\n", rid(query(1, L, ops[i].k)));
}
else {
modify(ops[i].i, a[ops[i].i], -1);
a[ops[i].i] = id(ops[i].t);
modify(ops[i].i, a[ops[i].i], 1);
}
}
return 0;
}
|