题解
动态查询区间k小值——树状数组套主席树( •̀ ω •́ )
如果直接主席树上进行动态修改，每次需要修改([l,r])区间内所有的根，时间复杂度为(O(nlogn))。主席树是前缀和，树状数组也是前缀和，而且还可以动态修改，巧了你们两个认识一下（
具体实现：主席树中以(rt_i)为根的子树存储的不再是第(i)个版本（([1,i])）的信息，而是lowbit区间中版本的信息（如同树状数组中的一个节点）。modify：与树状数组相仿，不过修改循环从(x)开始而非(1)（(a_x)的修改仅影响([x,n])的前缀和）。query：预处理出需要查询的主席树根（约(logn)个，以lowbit覆盖查询区间），统计左儿子中元素数量与转移时，预处理的每个根都进行一遍即可。
AC代码
#include<bits/stdc++.h>
#define lowb(x) x&(-x)
using namespace std;
const int N=1e5+10;
struct node {char op; int x,y,z;} q[N];
int rt[N],ls[N*200],rs[N*200],sum[N*200],tmp[2][20],cnt[2];
//tmp[1/0]:[1,r]/[1,l-1]区间内需要查询的根(节点),cnt[2]:需要查询的根数
int a[N],b[2*N],nn,n,tot;//b:离散化数组
void add(int &x,int l,int r,int pos,int v)
{
if(!x) x=++tot;
sum[x]+=v;
if(l==r) return;
int mid=(l+r)/2;
if(pos<=mid) add(ls[x],l,mid,pos,v);
else add(rs[x],mid+1,r,pos,v);
}
void p_add(int x,int v)
{
int k=lower_bound(b+1,b+nn+1,a[x])-b;//a[x]离散化后的值
for(int i=x;i<=n;i+=lowb(i)) add(rt[i],1,nn,k,v);
}
int ask(int l,int r,int k)
{
if(l==r) return l;
int num=0,mid=(l+r)/2;
for(int i=1;i<=cnt[1];i++) num+=sum[ls[tmp[1][i]]];
for(int i=1;i<=cnt[0];i++) num-=sum[ls[tmp[0][i]]];
if(k<=num)
{
for(int i=1;i<=cnt[1];i++) tmp[1][i]=ls[tmp[1][i]];
for(int i=1;i<=cnt[0];i++) tmp[0][i]=ls[tmp[0][i]];
return ask(l,mid,k);
}
for(int i=1;i<=cnt[1];i++) tmp[1][i]=rs[tmp[1][i]];
for(int i=1;i<=cnt[0];i++) tmp[0][i]=rs[tmp[0][i]];
return ask(mid+1,r,k-num);//!处理右儿子时k不要忘记-num
}
int p_ask(int l,int r,int k)
{
memset(tmp,0,sizeof(tmp));
cnt[0]=cnt[1]=0;
for(int i=r;i;i-=lowb(i)) tmp[1][++cnt[1]]=rt[i];
for(int i=l-1;i;i-=lowb(i)) tmp[0][++cnt[0]]=rt[i];
return ask(1,nn,k);
}
int main()
{
ios::sync_with_stdio(0);
int m,x,y,z; char op;
cin>>n>>m;
for(int i=1;i<=n;i++) {cin>>a[i]; b[++nn]=a[i];}
for(int i=1;i<=m;i++)
{
cin>>q[i].op;
if(q[i].op=='C') {cin>>q[i].x>>q[i].y; b[++nn]=q[i].y;}
else cin>>q[i].x>>q[i].y>>q[i].z;
}
sort(b+1,b+nn+1); nn=unique(b+1,b+nn+1)-b-1;
for(int i=1;i<=n;i++) p_add(i,1);
for(int i=1;i<=m;i++)
{
if(q[i].op=='C')
{
p_add(q[i].x,-1);
a[q[i].x]=q[i].y; p_add(q[i].x,1);
}
else cout<<b[p_ask(q[i].x,q[i].y,q[i].z)]<<endl;
}
return 0;
}