原 bzoj 的数据，WA + TLE

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, INF = 2e9;
int root[N << 2], a[N], idx;
int n, m;

struct Node
{
    int l, r;
}sgt[N << 2];
struct Splay
{
    int s[2];
    int size, cnt, p, v;

    void init(int _v, int _p)
    {
        v = _v, p = _p;
        size = cnt = 1;
    }
}tr[N << 3];

void out(int P)
{
	cout << tr[P].v << endl;
	if (tr[P].s[0]) out(tr[P].s[0]);
	if (tr[P].s[1]) out(tr[P].s[1]);
}

void pushup(int p)
{
    int ls = tr[p].s[0], rs = tr[p].s[1];
    tr[p].size = tr[ls].size + tr[rs].size + tr[p].cnt;
}

void rotate(int x)
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    if (z) tr[z].s[tr[z].s[1] == y] = x;
    tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
    pushup(y), pushup(x);
}

void splay(int &rt, int x, int k)
{
    while (tr[x].p != k)
    {
        int y = tr[x].p, z = tr[y].p;
        if (z != k)
        {
            if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
    if (!k) rt = x;
}

void insert(int &rt, int v)
{
    int u = rt, p = 0;
    while (tr[u].v != v && u) p = u, u = tr[u].s[v > tr[u].v];

    if (!u)
    {
        u = ++idx;
        tr[u].init(v, p);
        if (p) tr[p].s[v > tr[p].v] = u;
    }
    else ++ tr[u].cnt;

    splay(rt, u, 0);
}

void Remove(int &rt, int v)
{
    int u = rt, p = 0;
    while (tr[u].v != v) p = u, u = tr[u].s[v > tr[u].v];

    if (tr[u].cnt > 1) -- tr[u].cnt, splay(rt, u, 0);
    else
    {
        splay(rt, u, 0);
        int nxt = tr[u].s[1], pre = tr[u].s[0];
        while (tr[nxt].s[0]) nxt = tr[nxt].s[0];
        while (tr[pre].s[1]) pre = tr[pre].s[1];
        splay(rt, pre, 0), splay(rt, nxt, pre);
        tr[nxt].s[0] = 0;
        pushup(nxt), pushup(pre);
    }
}

int get_rank(int &rt, int v)
{
    int u = rt, k = 0;
    while (u)
    {
        if (tr[u].v > v) u = tr[u].s[0];
        else if (tr[u].v < v) k += tr[tr[u].s[0]].size + tr[u].cnt, u = tr[u].s[1];
        else return  k += tr[tr[u].s[0]].size + 1, splay(rt, u, 0), k;
    }

    return k;
}

void dfs(int u, int fa)
{
    insert(root[fa], tr[u].v);
    if (tr[tr[u].s[0]].v != -INF && tr[u].s[0]) dfs(tr[u].s[0], fa);
    if (tr[tr[u].s[1]].v != INF && tr[u].s[1]) dfs(tr[u].s[1], fa);
}

void build(int P, int l, int r)
{
    auto &p = sgt[P];
    p.l = l, p.r = r;
    insert(root[P], INF), insert(root[P], -INF);

    if (l == r)
    {
        insert(root[P], a[l]);
        return;
    }

    int mid = l + r >> 1;
	build(P << 1, l, mid);
    build(P << 1 | 1, mid + 1, r);
	dfs(root[P << 1], P);
    dfs(root[P << 1 | 1], P);
}

void modify(int P, int x, int y)
{
    auto &p = sgt[P];
    Remove(root[P], a[x]);
    insert(root[P], y);

    if (p.l == p.r) return;

    int mid = p.l + p.r >> 1;
    if (x <= mid) modify(P << 1, x, y);
    else modify(P << 1 | 1, x, y);
}

int get(int P, int l, int r, int v)
{
    auto &p = sgt[P];

    if (l <= p.l && p.r <= r)
        return get_rank(root[P], v) - 1;

    int mid = p.l + p.r >> 1, res = 0;
    if (l <= mid) res += get(P << 1, l, r, v);
    if (r > mid) res += get(P << 1 | 1, l, r, v);
    return res;
}

int ask(int l, int r, int k)
{
    int L = 0, R = 1e9;
    while (L < R)
    {
        int mid = L + R >> 1;
        if (get(1, l, r, mid) < k) L = mid + 1;
        else R = mid;
    }

    return L;
}

int read()
{
    int s = 0;
    char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) s = (s << 3) + (s << 1) + ch - '0', ch = getchar();
    return s;
}

int main()
{
    n = read(), m = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    build(1, 1, n);

	while (m --)
    {
        char op[2];
        scanf("%s", op);
        if (*op == 'C')
        {
            int x = read(), y = read();
            modify(1, x, y);
            a[x] = y;
        }
        else
        {
            int l = read(), r = read(), k = read();
            printf("%d\n", ask(l, r, k));
        }
    }
    return 0;
}