我以后再也不乱写字符了啊啊啊！
动态区间第 K 小模板，树状数组维护修改哪些线段树。
错误的原因：
1、树状数组询问的时候 x和y 忘了套上 root
2、字符乱判，万紫千红
3、离散化的数组要开两倍
#include<bits/stdc++.h>
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') f=(ch=='-')?-1:1,ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;
}
const int N=200005;
struct obj{int l,r,sz;}tr[N*72];
int len,b[N],a[N],cnt,root[N],rt[2][N],c[2],n,m,tot;
void update(int &u,int l,int r,int k,int x)
{
if(!u) u=++cnt;
// cout<<u<<' '<<l<<' '<<r<<' '<<k<<' '<<tr[u].sz<<endl;
tr[u].sz+=x;
if(l==r) return;
int mid=l+r>>1;
if(k<=mid) update(tr[u].l,l,mid,k,x);
else update(tr[u].r,mid+1,r,k,x);
return;
}
void add(int x,int k)
{
int y=lower_bound(b+1,b+len+1,a[x])-b;
// cout<<x<<' '<<a[x]<<' '<<y<<endl;
while(x<=n) update(root[x],1,len,y,k),x+=x&-x;
}
int query(int l,int r,int k)
{
if(l==r) return l;
int sum=0;
for(int i=1;i<=c[1];i++) sum+=tr[tr[rt[1][i]].l].sz;
for(int i=1;i<=c[0];i++) sum-=tr[tr[rt[0][i]].l].sz;
// cout<<sum<<' '<<l<<' '<<r<<endl;
int mid=l+r>>1;
if(k<=sum)
{
for(int i=1;i<=c[1];i++) rt[1][i]=tr[rt[1][i]].l;
for(int i=1;i<=c[0];i++) rt[0][i]=tr[rt[0][i]].l;
return query(l,mid,k);
}
else
{
for(int i=1;i<=c[1];i++) rt[1][i]=tr[rt[1][i]].r;
for(int i=1;i<=c[0];i++) rt[0][i]=tr[rt[0][i]].r;
return query(mid+1,r,k-sum);
}
}
int Query(int x,int y,int z)
{
c[0]=c[1]=0;
x--;
while(x) rt[0][++c[0]]=root[x],x-=x&-x;
while(y) rt[1][++c[1]]=root[y],y-=y&-y;
return query(1,len,z);
}
int x[N],y[N],z[N];
bool opt[N];
int main()
{
tot=n=read(),m=read();
for(int i=1;i<=n;i++) b[i]=a[i]=read();
for(int i=1;i<=m;i++)
{
char ch=getchar();
while(ch!='Q'&&ch!='C') ch=getchar();
if(ch=='Q') x[i]=read(),y[i]=read(),z[i]=read();
else opt[i]=true,x[i]=read(),b[++tot]=y[i]=read();
}
sort(b+1,b+tot+1),len=unique(b+1,b+tot+1)-b-1;
for(int i=1;i<=n;i++) add(i,1);
for(int i=1;i<=m;i++)
{
if(opt[i]) add(x[i],-1),a[x[i]]=y[i],add(x[i],1);
else printf("%d\n",b[Query(x[i],y[i],z[i])]);
}
return 0;
}
/*
5 1
1 2 3 4 5
Q 1 5 3
*/