动态排名 / Dynamic Rankings
题目链接：ybt金牌导航4-6-6 / luogu P2617 / ybt金牌导航4-7-4
题目大意
要你支持可修改的区间第 k 小。
思路
看到题目，情不自禁地想到了可插入可修改的区间第 k 小（什么直接上替罪羊套线段树）。
但是很明显没有插入操作，可以不用平衡树。
那重新搞，先看没有修改，那就是直接一个主席树就完事。
那如果多了修改，我们考虑到修改一个点 (x) 会对 (xsim n) 的线段树都会产生影响，显然你要一个一个修改，时间就炸了。
那你考虑到前缀和的查询是 (O(1))，非常优秀，但它有着修改 (O(n)) 的确定。
那我们考虑用另一个数据结构来代替，使得它查询和修改都能比较小（比如 (O(1),O(sqrt{n}),O(logn))）
然后你就想到了查询和修改都是 (O(logn)) 的树状数组。
那我们就把外面的前缀和改成树状数组，每次要放一个点进去，就树状数组找它影响的位置，然后在这些位置对于的线段树中这个位置放这个数。
然后查询就是先树状数组找出影响着两个位置的线段树。（因为我们还是要用前缀和来统计，所以找的是 (x-1) 和 (y)）
然后就在树上二分，每次所有位置全部往左 / 往右走。
（这个其实就是带修主席树，不过理解成树状数组套线段树也可以）
然后修改操作就相当于在这个位置中把之前的数删掉，然后再放入你现在的数。
那就分解成两个前面一样的操作了。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Tree {
int l, r, val;
}t[100001 << 8];
int D, n, m, rt[100001], tot, x[100001], y[100001], z[100001];
int a[100001], b[200001], ts[2][30];
char op[100001];
int read() {
int re = 0;
char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') {
re = (re << 3) + (re << 1) + c - '0';
c = getchar();
}
return re;
}
void insert(int &now, int l, int r, int pl, int num) {//在线段树中插入一个点
if (!now) now = ++tot, t[now] = (Tree){0, 0, 0};
t[now].val += num;
if (l != r) {
int mid = (l + r) >> 1;
if (pl <= mid) insert(t[now].l, l, mid, pl, num);
else insert(t[now].r, mid + 1, r, pl, num);
}
}
void insert_(int x, int num) {
int pl = lower_bound(b + 1, b + b[0] + 1, a[x]) - b;
for (; x <= n; x += x & (-x)) insert(rt[x], 1, b[0], pl, num);//树状数组看它会影响到的位置，然后里面都加点
}
int query(int l, int r, int rnk) {
if (l == r) return l;
int mid = (l + r) >> 1;
int re = 0;
for (int i = 1; i <= ts[1][0]; i++)//都往左走，用前缀和的方法统计满足的数个数
re += t[t[ts[1][i]].l].val;
for (int i = 1; i <= ts[0][0]; i++)
re -= t[t[ts[0][i]].l].val;
if (re >= rnk) {//根据结果二分（所有点都向左 / 向右走）
for (int i = 1; i <= ts[1][0]; i++)
ts[1][i] = t[ts[1][i]].l;
for (int i = 1; i <= ts[0][0]; i++)
ts[0][i] = t[ts[0][i]].l;
return query(l, mid, rnk);
}
else {
for (int i = 1; i <= ts[1][0]; i++)
ts[1][i] = t[ts[1][i]].r;
for (int i = 1; i <= ts[0][0]; i++)
ts[0][i] = t[ts[0][i]].r;
return query(mid + 1, r, rnk - re);
}
}
int query_(int x, int y, int z) {
memset(ts, 0, sizeof(ts));//把计算它的点全部找出来
for (int xx = x - 1; xx; xx -= xx & (-xx)) ts[0][++ts[0][0]] = rt[xx];//记得这里是前缀和，所以是 x-1
for (int yy = y; yy; yy -= yy & (-yy)) ts[1][++ts[1][0]] = rt[yy];
return b[query(1, b[0], z)];
}
int main() {
n = read(); m = read();
for (int i = 1; i <= n; i++) {
a[i] = read();
b[++b[0]] = a[i];
}
for (int i = 1; i <= m; i++) {
op[i] = getchar();
while (op[i] != 'Q' && op[i] != 'C') op[i] = getchar();
if (op[i] == 'Q') x[i] = read(), y[i] = read(), z[i] = read();
else x[i] = read(), y[i] = read(), b[++b[0]] = y[i];
}
sort(b + 1, b + b[0] + 1);//离散化
b[0] = unique(b + 1, b + b[0] + 1) - b - 1;
for (int i = 1; i <= n; i++)
insert_(i, 1);
for (int i = 1; i <= m; i++) {
if (op[i] == 'C') {//替换就相当于在这个位置减掉之间的，再加现在的
insert_(x[i], -1);
a[x[i]] = y[i];
insert_(x[i], 1);
}
else {
printf("%d
", query_(x[i], y[i], z[i]));
}
}
return 0;
}