题意

有一个长度为 $n$ 的序列，要支持单点修改，区间查询第 $k$ 大。

分析

区间第 $k$ 大就是主席树板子，但是有一个修改操作，我们不喜欢带修整体二分，于是就有了动态主席树。

我们知道，单次修改会使得一段后缀的线段树都变化。这样子时间复杂度就是 $O(n^2\log n)$，直接爆炸。

我们参考单点修改，区间求和的思路。在那一题中，我们如果没有修改操作，可以直接前缀和。但是有了修改之后，单点修改就会影响到 $O(n)$ 个值。我们使用了树状数组，做到每一次只会影响到 $O(\log n)$ 个值，查询也变成了 $O(\log n)$ 的。

放到这题，我们也可以使用树状数组。我们每次修改的时候直接修改树状数组上对应的节点，每次只会影响到 $O(\log n)$ 棵树。查询的时候就先处理出 $r$ 对应的点和 $l - 1$ 对应的点，再差分。这样子总的时间复杂度就是 $O(n\log^2n)$ 的。时间复杂度非常的好。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 100005
il ll rd(){
    ll s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
char op;
int n, m, a[N], nls[N << 1], cnt, tmp[2][N], ct[2], l, r, c;
int tr[N * 400], ls[N * 400], rs[N * 400], rt[N], ep;
struct Q{
    int l, r, c;
}q[N];
void add(int &p, int l, int r, int x, int k){
    if (!p) p = ++ep;
    tr[p] += k;
    if (l == r) return ;
    int mid = (l + r) >> 1;
    if (x <= mid) add(ls[p], l, mid, x, k);
    else add(rs[p], mid + 1, r, x, k);
}
int query(int l, int r, int k){
    if (l == r) return l;
    int mid = (l + r) >> 1, x = 0;
    for (int i = 1; i <= ct[0]; i++) x += tr[ls[tmp[0][i]]];
    for (int i = 1; i <= ct[1]; i++) x -= tr[ls[tmp[1][i]]];
    if (k <= x){
        for (int i = 1; i <= ct[0]; i++) tmp[0][i] = ls[tmp[0][i]];
        for (int i = 1; i <= ct[1]; i++) tmp[1][i] = ls[tmp[1][i]];
        return query(l, mid, k);
    }
    else{
        for (int i = 1; i <= ct[0]; i++) tmp[0][i] = rs[tmp[0][i]];
        for (int i = 1; i <= ct[1]; i++) tmp[1][i] = rs[tmp[1][i]];
        return query(mid + 1, r, k - x);
    }
}
il void insert(int x, int k){for (int i = x; i <= n; i += (i & (-i))) add(rt[i], 1, cnt, a[x], k);}
il int ask(int l, int r, int k){
    for (int i = 1; i <= ct[0]; i++) tmp[0][i] = 0;
    for (int i = 1; i <= ct[1]; i++) tmp[1][i] = 0;
    ct[0] = ct[1] = 0;
    for (int i = r; i >= 1; i -= (i & (-i))) tmp[0][++ct[0]] = rt[i];
    for (int i = l - 1; i >= 1; i -= (i & (-i))) tmp[1][++ct[1]] = rt[i];
    return nls[query(1, cnt, k)];
}
int main(){
    n = rd(), m = rd();
    for (int i = 1; i <= n; i++) a[i] = rd(), nls[++cnt] = a[i];
    for (int i = 1; i <= m; i++){
        cin >> op;
        if (op == 'Q') l = rd(), r = rd(), c = rd(), q[i] = Q{l, r, c};
        else l = rd(), c = rd(), q[i] = Q{-1, l, c}, nls[++cnt] = c;
    }
    sort (nls + 1, nls + cnt + 1);
    cnt = unique(nls + 1, nls + cnt + 1) - nls - 1;
    for (int i = 1; i <= n; i++) a[i] = lower_bound(nls + 1, nls + cnt + 1, a[i]) - nls, insert(i, 1);
    for (int i = 1; i <= m; i++) if (q[i].l == -1) q[i].c = lower_bound(nls + 1, nls + cnt + 1, q[i].c) - nls;
    for (int i = 1; i <= m; i++){
        if (q[i].l == -1){
            l = q[i].r, c = q[i].c;
            insert(l, -1), a[l] = c, insert(l, 1);
        }else{
            l = q[i].l, r = q[i].r, c = q[i].c;
            printf ("%d\n", ask(l, r, c));
        }
    }
    return 0;
}