「BZOJ-1901」Zju2112 Dynamic Rankings-主席树+树状数组

给定一个含有 n 个数的序列 a[1],a[2],a[3], … ,a[n],程序必须回答这样的询问:对于给定的 i,j,k,在 a[i],a[i+1],a[i+2], … ,a[j] 中第 k 小的数是多少 (1≤k≤j-i+1),并且,你可以改变一些a[i]的值,改变后,程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序,从输入文件中读入序列 a,然后读入一系列的指令,包括询问指令和修改指令。对于每一个询问指令,你必须输出正确的回答。 第一行有两个正整数 n(1≤n≤10000),m(1≤m≤10000)。分别表示序列的长度和指令的个数。第二行有 n 个数,表示 a[1],a[2]……a[n],这些数都小于 10^9。接下来的 m 行描述每条指令,每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t Q i j k (i,j,k是数字,1≤i≤j≤n, 1≤k≤j-i+1) 表示询问指令,询问 a[i],a[i+1]……a[j] 中第 k 小的数。C i t (1≤i≤n,0≤t≤10^9) 表示把 a[i] 改变成为 t。

链接

bzoj1901

输入

对于每一次询问,你都需要输出他的答案,每一个输出占单独的一行。

样例数据

输入

1
2
3
4
5
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

输出

1
2
3
6

题解

裸的树状数组套主席树…

代码

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;
}
分享到