这是一道练习树套树的好题, 只不过窝不会 w.

所以开始考虑用分块乱搞. 首先对序列分块, 然后对权值分块. 维护 $sma_{i,j}$ 表示 序列 前 $i$ 块中的数,值 在第 $j$ 块中的数的个数, $smb_{i,j}$ 表示 序列 前 $i$ 块中的数,值 为 $j$ 的数的个数, 之后的询问和修改操作都围绕这两个块来进行.

对于一个区间 $[L,R]$ 的询问, 如果 $[L,R]$ 在同一块内暴力做. 否则, 先暴力的处理两个数组 $smc_{i},smd_{i}$ 分别表示在两侧不完整的块中 值在第 $i$ 块中的数的个数和 值为 $i$ 的数的个数. 暴力枚举每一个 值域 分成的块, 可以利用 $sma$ 和 $smc$ , $\Theta(1)$ 地求出区间内范围在这一块中数的个数, 确定答案在哪一块中. 再暴力枚举那一块中每一个数, 确定最终答案.

Code

// a[i]:第i个位置上的数(已离散化) b[i]:序列第i个位置所在块编号 c[i]:i这个数所在块编号
// s:序列分块的块大小 ss:值域分块的块大小
x=ri[i]/*L*/; y=rj[i]/*R*/; z=rk[i]/*k*/; f=true;
if (b[x]==b[y]) {/*同一块中暴力做*/}
else {
    for (int j=(b[x]+1)*s;j>=x;--j) {++smc[c[a[j]]]; ++smd[a[j]];}
    for (int j=b[y]*s+1;j<=y;++j) {++smc[c[a[j]]]; ++smd[a[j]];} // 处理出smc和smd
    for (int j=0;j<=ss&&f;++j) /*枚举值域块*/ {
        if (z<=(r=sma[b[y]-1][j]-sma[b[x]][j]+smc[j])) /*如果在这一块内*/
            for (int k=j*ss+1;;++k) /*枚举块内的每一个值*/ {
                if (z<=(r=smb[b[y]-1][k]-smb[b[x]][k]+smd[k])) {
                    print(d[k]); f=false; break;
                } z-=r;
            } z-=r;
    }
    for (int j=(b[x]+1)*s;j>=x;--j) {--smc[c[a[j]]]; --smd[a[j]];}
    for (int j=b[y]*s+1;j<=y;++j) {--smc[c[a[j]]]; --smd[a[j]];} // 清空smc和smd,不能用memset,否则复杂度就变成了O(n)
}

对于一个修改操作, 只需要暴力地修改之后每一个块对应的前缀和即可.

x=ri[i]/*修改位置*/; y=rj[i]/*修改目标值*/;
for (int j=b[x];j<=s;++j) {
    --sma[j][c[a[x]]]; ++sma[j][c[y]];
    --smb[j][a[x]]; ++smb[j][y];
} a[x]=y;

修改和更新复杂度都是 $\Theta(n \sqrt{n})$ ($n,m$ 同级), 离散化一下即可过 $50%$ 的点. 代码:

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include <algorithm>
#include <immintrin.h>
#include <emmintrin.h>
#include <cmath>
#include <cstdio>
using namespace std;

int n,m,s,ss,ms,a[100005],b[100005],c[200005],d[200005];
int sma[325][455],smb[325][200005],smc[455],smd[200005];
int ri[100005],rj[100005],rk[100005];
bool rf[100005];

#define gc() (p0==p1&&(p1=(p0=buf0)+fread(buf0,1,16777216,stdin),p0==p1)?EOF:*p0++)
char buf0[16777217],*p0,*p1;
inline int read() {
    int ret=0; char ch=gc(); while (ch<48||ch>57) ch=gc();
    while (ch>47&&ch<58) {ret=(ret<<3)+(ret<<1)+(ch^48); ch=gc();}
    return ret;
}

char buf1[16777217],stk[23]; int p2,p3 = -1;
inline void flush() {
    fwrite(buf1,1,p3+1,stdout), p3 = -1;
}
inline void print(int x)
{
    if (p3>8388608) flush();
    do stk[++p2]=x%10+48; while (x/=10);
    do buf1[++p3]=stk[p2]; while (--p2);
    buf1[++p3]='\n';
}

int main() {
    int x,y,z,r; char ch; bool f;
    n=ms=read(); m=read();
    for (int i=1;i<=n;++i) a[i]=d[i]=read();
    for (int i=0;i<m;++i) {
        do ch=gc(); while (ch!=67&&ch!=81);
        if (ch==67) {ri[i]=read(); rj[i]=d[++ms]=read(); rf[i]=true;}
        else {ri[i]=read(); rj[i]=read(); rk[i]=read();}
    }
    sort(d+1,d+ms+1);
    for (int i=1;i<=n;++i) a[i]=lower_bound(d+1,d+ms+1,a[i])-d;
    for (int i=0;i<m;++i) if (rf[i]) rj[i]=lower_bound(d+1,d+ms+1,rj[i])-d;
    ss=(int)sqrt(ms); for (int i=1;i<=s;++i) c[i]=(i-1)/ss;
    s=(int)sqrt(n); for (int i=1;i<=n;++i) b[i]=(i-1)/s;
    for (int i=1;i<=n;++i) {
        ++sma[b[i]][c[a[i]]];
        ++smb[b[i]][a[i]];
    }
    for (int i=1;i<=s;++i) {
        for (int j=0;j<=ss;++j) sma[i][j]+=sma[i-1][j];
        for (int j=0;j<=ms;++j) smb[i][j]+=smb[i-1][j];
    }
    for (int i=0;i<m;++i) {
        if (rf[i]) {
            x=ri[i]; y=rj[i];
            for (int j=b[x];j<=s;++j) {
                --sma[j][c[a[x]]]; ++sma[j][c[y]];
                --smb[j][a[x]]; ++smb[j][y];
            } a[x]=y;
        }
        else {
            x=ri[i]; y=rj[i]; z=rk[i]; f=true;
            if (b[x]==b[y]) {
                for (int j=x;j<=y;++j) {++smc[c[a[j]]]; ++smd[a[j]];}
                for (int j=0;j<=ss&&f;++j) {
                    if (z<=smc[j])
                        for (int k=j*ss+1;;++k) {
                            if (z<=smd[k]) {
                                print(d[k]); f=false; break;
                            } z-=smd[k];
                        } z-=smc[j];
                }
                for (int j=x;j<=y;++j) {--smc[c[a[j]]]; --smd[a[j]];}
            }
            else {
                for (int j=(b[x]+1)*s;j>=x;--j) {++smc[c[a[j]]]; ++smd[a[j]];}
                for (int j=b[y]*s+1;j<=y;++j) {++smc[c[a[j]]]; ++smd[a[j]];}
                for (int j=0;j<=ss&&f;++j) {
                    if (z<=(r=sma[b[y]-1][j]-sma[b[x]][j]+smc[j]))
                        for (int k=j*ss+1;;++k) {
                            if (z<=(r=smb[b[y]-1][k]-smb[b[x]][k]+smd[k])) {
                                print(d[k]); f=false; break;
                            } z-=r;
                        } z-=r;
                }
                for (int j=(b[x]+1)*s;j>=x;--j) {--smc[c[a[j]]]; --smd[a[j]];}
                for (int j=b[y]*s+1;j<=y;++j) {--smc[c[a[j]]]; --smd[a[j]];}
            }
        }
    } flush(); return 0;
}