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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define maxn 100010
#define logn 18
#define pb push_back
#define lowbit(i) ((i) & (-i))
using namespace std;
int n, m, a[maxn];
struct Query {
int opt, id, x, y, z;
} Q[maxn];
int b[maxn * 2], cnt;
void init_hash() {
for (int i = 1; i <= n; ++i) b[i] = a[i]; int c1 = n;
for (int i = 1; i <= m; ++i) {
if (Q[i].opt == 0) continue;
b[++c1] = Q[i].y;
}
sort(b + 1, b + c1 + 1); cnt = unique(b + 1, b + c1 + 1) - b - 1;
for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
for (int i = 1; i <= m; ++i) {
if (Q[i].opt == 0) continue;
Q[i].y = lower_bound(b + 1, b + cnt + 1, Q[i].y) - b;
}
}
#define lc T[i].ch[0]
#define rc T[i].ch[1]
#define Lc T[j].ch[0]
#define Rc T[j].ch[1]
struct zhuxi {
int v, ch[2];
} T[maxn * logn + 2 * maxn * logn * logn]; int rt[maxn * 2], top;
void update(int &i, int j, int l, int r, int k, int v) {
i = ++top; T[i] = T[j]; T[i].v += v;
if (l == r) return ; int m = l + r >> 1;
if (k <= m) update(lc, Lc, l, m, k, v);
else update(rc, Rc, m + 1, r, k, v);
}
vector<int> a1, a2;
int query(int i, int j, int l, int r, int k) {
int v = T[Lc].v - T[lc].v, m = l + r >> 1; if (l == r) return l;
for (auto u : a1) v -= T[T[u].ch[0]].v;
for (auto u : a2) v += T[T[u].ch[0]].v;
if (k <= v) {
for (auto &u : a1) u = T[u].ch[0];
for (auto &u : a2) u = T[u].ch[0];
return query(lc, Lc, l, m, k);
}
else {
for (auto &u : a1) u = T[u].ch[1];
for (auto &u : a2) u = T[u].ch[1];
return query(rc, Rc, m + 1, r, k - v);
}
}
void add(int i, int v) {
int k = a[i];
while (i <= n) update(rt[i + n], rt[i + n], 1, cnt, k, v), i += lowbit(i);
}
inline void solve_0(int i) {
int l = Q[i].x, r = Q[i].y, k = Q[i].z; a1.clear(); a2.clear();
for (int i = l - 1; i; i -= lowbit(i)) a1.pb(rt[i + n]);
for (int i = r; i; i -= lowbit(i)) a2.pb(rt[i + n]);
printf("%d\n", b[query(rt[l - 1], rt[r], 1, cnt, k)]);
}
inline void solve_1(int i) {
int x = Q[i].x, y = Q[i].y;
add(x, -1); a[x] = y; add(x, 1);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= m; ++i) {
char c[3]; scanf("%s%d%d", c, &Q[i].x, &Q[i].y);
if (c[0] == 'Q') scanf("%d", &Q[i].z), Q[i].opt = 0;
else Q[i].opt = 1;
} init_hash();
for (int i = 1; i <= n; ++i) update(rt[i], rt[i - 1], 1, cnt, a[i], 1);
for (int i = 1; i <= m; ++i) {
int opt = Q[i].opt;
if (!Q[i].opt) solve_0(i);
else solve_1(i);
}
return 0;
}
|