动态区间第k小

离散化后

那么每个点开一棵线段树（主席树）再套一个树状数组在外面

每次询问区间内的树的个数时
相当于进行了一次树状数组求区间和的操作，只是是把树状数组那个点看做主席树，对log棵主席树求区间和

然后每次询问，修改时就是把log棵主席树同时跳到儿子，修改也是log棵

时间复杂度O（nlogn*logn）空间复杂度O（nlogn*logn）

# include <bits/stdc++.h>

# define IL inline

# define RG register

# define Fill(a, b) memset(a, b, sizeof(a))

using namespace std;

typedef long long ll;

const int _(2e4 + 10), __(2e6 + 10);

IL ll Read(){

    RG char c = getchar(); RG ll x = 0, z = 1;

    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;

    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);

    return x * z;

}

int n, m, len, p[_], a[_], ql[_], qr[_], qk[_], qo[_];

int ls[__], rs[__], sz[__], rt[__], num, tmp[2][20];

IL void Modify(RG int &x, RG int l, RG int r, RG int pos, RG int val){

    if(!x) x = ++num;

    sz[x] += val;

    if(l == r) return;

    RG int mid = (l + r) >> 1;

    if(pos <= mid) Modify(ls[x], l, mid, pos, val);

    else Modify(rs[x], mid + 1, r, pos, val);

}

IL void PreModify(RG int x, RG int val){

    RG int k = lower_bound(p + 1, p + len + 1, a[x]) - p;

    for(RG int i = x; i <= n; i += i & -i) Modify(rt[i], 1, len, k, val);

}

IL int Query(RG int l, RG int r, RG int k){

    if(l == r) return l;

    RG int mid = (l + r) >> 1, sum = 0;

    for(RG int i = 1; i <= tmp[1][0]; i++) sum += sz[ls[tmp[1][i]]];

    for(RG int i = 1; i <= tmp[0][0]; i++) sum -= sz[ls[tmp[0][i]]];

    if(k <= sum){

        for(RG int i = 1; i <= tmp[1][0]; i++) tmp[1][i] = ls[tmp[1][i]];

        for(RG int i = 1; i <= tmp[0][0]; i++) tmp[0][i] = ls[tmp[0][i]];

        return Query(l, mid, k);

    }

    else{

        for(RG int i = 1; i <= tmp[1][0]; i++) tmp[1][i] = rs[tmp[1][i]];

        for(RG int i = 1; i <= tmp[0][0]; i++) tmp[0][i] = rs[tmp[0][i]];

        return Query(mid + 1, r, k - sum);

    }

}

IL int PreQuery(RG int l, RG int r, RG int k){

    Fill(tmp, 0);

    for(RG int i = r; i; i -= i & -i) tmp[1][++tmp[1][0]] = rt[i];

    for(RG int i = l - 1; i; i -= i & -i) tmp[0][++tmp[0][0]] = rt[i];

    return Query(1, len, k);

}

int main(RG int argc, RG char* argv[]){

    n = Read(); m = Read();

    for(RG int i = 1; i <= n; i++) a[i] = Read(), p[++len] = a[i];

    for(RG int i = 1; i <= m; i++){

        RG char c; scanf(" %c", &c);

        qo[i] = c == 'Q';

        if(qo[i]) ql[i] = Read(), qr[i] = Read(), qk[i] = Read();

        else ql[i] = qr[i] = Read(), qk[i] = Read(), p[++len] = qk[i];

    }

    sort(p + 1, p + len + 1); len = unique(p + 1, p + len + 1) - p - 1;

    for(RG int i = 1; i <= n; i++) PreModify(i, 1);

    for(RG int i = 1; i <= m; i++)

        if(qo[i]) printf("%d\n", p[PreQuery(ql[i], qr[i], qk[i])]);

        else{

            PreModify(ql[i], -1);

            a[ql[i]] = qk[i];

            PreModify(ql[i], 1);

        }

    return 0;

}