外面是树状数组，里面是动态开点线段树，对于查询我们先把有关点找出来，然后一起在线段树上行走，这样就是单个O(log2)的了
#include <cstdio>
#include <vector>
#include <cstring>
#define R register
#define Inf 1000000000
#define MAXN 50000
using namespace std;
inline int read()
{
R int sum=;
R char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch>=''&&ch<='')
{
sum=(sum<<)+(sum<<)+ch-'';
ch=getchar();
}
return sum;
}
struct Seg_Tree
{
Seg_Tree *ch[];
int l,r,size;
void pushup()
{
size=ch[]->size+ch[]->size;
}
}*null,*root[MAXN+];
typedef vector<Seg_Tree*> S;
char s[];
int a[MAXN+];
inline Seg_Tree *New(int l,int r)
{
Seg_Tree *p=new Seg_Tree;
p->l=l,p->r=r,p->size=;
p->ch[]=p->ch[]=null;
return p;
}
int n,m;
void ins(Seg_Tree *p,int key)
{
if(p->l==p->r)
{
p->size++;
return;
}
if(key<=((p->l+p->r)>>))
{
if(p->ch[]==null)p->ch[]=New(p->l,((p->l+p->r)>>));
ins(p->ch[],key);
}
else
{
if(p->ch[]==null)p->ch[]=New(((p->l+p->r)>>)+,p->r);
ins(p->ch[],key);
}
p->pushup();
}
inline void Ins(int pos,int key)
{
while(pos<=n)
{
if(root[pos]==null)root[pos]=New(,Inf);
ins(root[pos],key);
pos+=pos&(-pos);
}
}
void del(Seg_Tree *&p,int key)
{
if(p->l==p->r)
{
p->size--;
if(p->size==){ delete p; p=null; }
return;
}
if(key<=((p->l+p->r)>>))del(p->ch[],key);
else del(p->ch[],key);
p->pushup();
if(p->size==){ delete p; p=null; }
}
inline void Del(int pos,int key)
{
while(pos<=n)
{
del(root[pos],key);
pos+=pos&(-pos);
}
}
inline void Init()
{
null=New(,),n=read(),m=read();
null->ch[]=null->ch[]=null;
for(R int i=;i<=n;i++)root[i]=null;
for(R int i=;i<=n;i++)
a[i]=read(),Ins(i,a[i]);
}
inline S Catch(int pos)
{
S v;v.clear();
while(pos)
{
v.push_back(root[pos]);
pos-=pos&(-pos);
}
return v;
}
inline S get_ch0(S v)
{
for(R int i=;i<v.size();++i)v[i]=v[i]->ch[];
return v;
}
inline S get_ch1(S v)
{
for(R int i=;i<v.size();++i)v[i]=v[i]->ch[];
return v;
}
int query(S v1,S v2,int k,int z,int y)
{
if(z==y)return z;
R int sum=;
for(int i=;i<v2.size();i++)sum+=v2[i]->ch[]->size;
for(int i=;i<v1.size();i++)sum-=v1[i]->ch[]->size;
if(sum>=k) return query(get_ch0(v1),get_ch0(v2),k,z,(z+y)>>);
else return query(get_ch1(v1),get_ch1(v2),k-sum,((z+y)>>)+,y);
}
inline void Work()
{
R int x,y,z;
while(m--)
{
scanf("%s",s);
if(s[]=='C')
{
x=read(),y=read();
Del(x,a[x]),Ins(x,y);
a[x]=y;
continue;
}
else
{
x=read(),y=read(),z=read();
printf("%d\n",query(Catch(x-),Catch(y),z,,Inf));
}
}
}
void CL(Seg_Tree *p)
{
if(p==null)return;
CL(p->ch[]);
CL(p->ch[]);
delete p;
}
inline void Clear()
{
for(int i=;i<=n;i++)CL(root[i]),root[i]=NULL;
delete null;null=NULL;
}
int main()
{
freopen("dynrank.in","r",stdin);
freopen("dynrank.out","w",stdout);
R int T=read();
while(T--)
{
Init();
Work();
Clear();
}
}