https://www.luogu.com.cn/record/109659611

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 100005
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define ts(p) tree[p].size
#define tl(p) tree[p].l
#define tr(p) tree[p].r
#define td(p) tree[p].dat
#define tv(p) tree[p].val
#define son(p, d) tree[p].son[d]
#define Rt(p) tree[p].root
#define tc(p) tree[p].cnt
inline int ls(int p)
{
    return p << 1;
}
inline int rs(int p)
{
    return p << 1 | 1;
}
inline int read()
{
    int x = 0, f = 1;
    register char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int n, m, a[N];
namespace Treap
{
    struct balance
    {
        int size, dat, son[2], cnt, val;
    } tree[N << 7];
    int tot;
    void pushup(int p)
    {
        ts(p) = ts(son(p, 0)) + ts(son(p, 1)) + tc(p);
    }
    int New(int v)
    {
        tv(++tot) = v;
        td(tot) = rand();
        ts(tot) = tc(tot) = 1;
        son(tot, 0) = son(tot, 1) = 0;
        return tot;
    }
    void rotate(int &p, int d)
    {
        int tmp = son(p, d);
        son(p, d) = son(tmp, d ^ 1);
        son(tmp, d ^ 1) = p;
        pushup(p), pushup(tmp);
        p = tmp;
    }
    void insert(int &p, int v)
    {
        if (!p)
            p = New(v);
        else if (v == tv(p))
            ++tc(p);
        else
        {
            int r = tv(p) < v;
            insert(son(p, r), v);
            if (td(son(p, r)) > td(p))
                rotate(p, r);
        }
        pushup(p);
    }
    void remove(int &p, int v)
    {
        if (tv(p) > v)
            remove(son(p, 0), v);
        else if (tv(p) < v)
            remove(son(p, 1), v);
        else
        {
            if (tc(p) > 1)
                --tc(p);
            else
            {
                if (!son(p, 0) && !son(p, 1))
                    p = 0;
                else if (!son(p, 0))
                    rotate(p, 1), remove(son(p, 0), v);
                else if (!son(p, 1))
                    rotate(p, 0), remove(son(p, 1), v);
                else
                {
                    if (td(son(p, 0)) > td(son(p, 1)))
                        rotate(p, 0), remove(son(p, 1), v);
                    else
                        rotate(p, 1), remove(son(p, 0), v);
                }
            }
        }
        if (p)
            pushup(p);
    }
    int get_rank(int p, int v)
    {
        if (!p)
            return 0;
        if (tv(p) > v)
            return get_rank(son(p, 0), v);
        else if (tv(p) == v)
            return ts(son(p, 0));
        else
            return get_rank(son(p, 1), v) + ts(son(p, 0)) + tc(p);
    }
}
namespace SEG
{
    struct segment
    {
        int l, r, root;
    } tree[N << 3];
    void build(int p, int l, int r)
    {
        tl(p) = l, tr(p) = r;
        rep(i, l, r) Treap::insert(Rt(p), a[i]);
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        build(ls(p), l, mid);
        build(rs(p), mid + 1, r);
    }
    void modify(int p, int x, int k)
    {
        Treap::remove(Rt(p), a[x]);
        Treap::insert(Rt(p), k);
        if (tl(p) == tr(p))
            return;
        int mid = (tl(p) + tr(p)) >> 1;
        if (x > mid)
            modify(rs(p), x, k);
        else
            modify(ls(p), x, k);
    }
    int query_rank(int p, int l, int r, int v)
    {
        if (tl(p) > r || tr(p) < l)
            return 0;
        else if (tl(p) >= l && tr(p) <= r)
            return Treap::get_rank(Rt(p), v);
        else
            return query_rank(ls(p), l, r, v) + query_rank(rs(p), l, r, v);
    }
    int query_val(int l, int r, int rk)
    {
        int u = 0, v = 1e9;
        while (u < v)
        {
            int mid = (u + v + 1) >> 1;
            if (query_rank(1, l, r, mid) < rk)
                u = mid;
            else
                v = mid - 1;
        }
        return v;
    }
}
signed main()
{
    n = read(), m = read();
    rep(i, 1, n) a[i] = read();
    SEG::build(1, 1, n);
    rep(i, 1, m)
    {
        char opt;
        cin >> opt;
        if (opt == 'Q')
        {
            int l = read(), r = read(), k = read();
            printf("%d\n", SEG::query_val(l, r, k));
        }
        else if (opt == 'C')
        {
            int x = read(), y = read();
            SEG::modify(1, x, y);
            a[x] = y;
        }
    }
    return 0;
}