题目大意：
动态单点更新，然后多次询问求区间内第k大
这里单个的主席树不能实现，这里采取的是树状数组套主席树
首先可以想的是将静态主席树先构建好，不去动它，这里空间复杂度就是O(nlogn)，这个只要之前做过主席树的入门题的话就都不是问题
然后考虑更新的情况，这里将更新产生的前缀变化保存在树状数组中，那么每次更新都要更新logn棵树状数组上的主席树，每一棵的更新操作都是
logn次的，那么时间复杂度就是nlognlogn的只是可以承受的
之后的询问也是，预处理好用到的树状数组，然后保存到向量中，不断处理更新的值
#include <bits/stdc++.h> using namespace std;
#define N 120010
#define lowbit(x) x&(-x)
#define define_m int m=(l+r)>>1
#define LS(x) node[x].ls
#define RS(x) node[x].rs vector<int> v1,v2; struct Node{
int ls , rs , sz;
Node(int ls= , int rs= , int sz=):ls(ls),rs(rs),sz(sz){}
void init(){ls=rs=sz=;}
}node[N*];
int tot , T1[N] , T2[N] , n , m , val[N]; //T1表示普通节点上的静态主席树，T2表示树状数组上的前缀树
int op[N] , s[N] , t[N] , rank[N]; int Hash(int v){return lower_bound(val , val+n , v)-val+;} int build(int l , int r)
{
int u = tot++;
node[u].init();
define_m;
if(l!=r){
LS(u) = build(l , m);
RS(u) = build(m+ , r);
}
return u;
} void build(int o1 , int o2 , int l , int r , int pos , int v , int i)
{
if(l==r){
node[o2].sz = node[o1].sz+v;
return;
}
define_m;
node[tot].init();
if(m>=pos){
LS(o2) = tot++ , RS(o2) = RS(o1);
build(LS(o1) , LS(o2) , l , m , pos , v , i);
}else{
LS(o2) = LS(o1) , RS(o2) = tot++;
build(RS(o1) , RS(o2) , m+ , r , pos , v , i);
}
node[o2].sz = node[LS(o2)].sz+node[RS(o2)].sz;
// cout<<"build : "<<i<<" "<<node[o2].sz<<" "<<l<<" "<<r<<" "<<pos<<endl;
} void update(int o , int l , int r , int pos , int v)
{
// cout<<pos<<" "<<l<<" "<<r<<" "<<v<<endl;
if(l==r){
node[o].sz += v;
return;
}
define_m;
if(m>=pos) {
if(!LS(o)){
LS(o) = tot++;
node[LS(o)].init();
}
update(LS(o) , l , m , pos , v);
}
else {
if(!RS(o)){
RS(o) = tot++;
node[RS(o)].init();
}
update(RS(o) , m+ , r , pos , v);
}
node[o].sz = node[LS(o)].sz+node[RS(o)].sz;
} void add(int x , int pos , int v)
{
while(x<=n){
if(!T2[x]){
node[tot].init();
T2[x] = tot++;
}
update(T2[x] , , n , pos , v);
x += lowbit(x);
}
} int query(vector<int> v1 , vector<int> v2 , int o1 , int o2 , int l , int r , int k)
{
// cout<<"fuck: "<<l<<" "<<r<<" "<<k<<endl;
if(l==r) return l;
define_m;
int c1 = node[LS(o2)].sz-node[LS(o1)].sz , l1=v1.size() , l2=v2.size();
// cout<<"st: "<<l1<<" "<<l2<<" "<<o1<<" "<<o2<<" "<<node[LS(o2)].sz<<" "<<node[LS(o1)].sz<<" "<<l<<" "<<r<<" "<<k<<endl;
for(int i= ; i<l1 ; i++){ c1-=node[LS(v1[i])].sz;
}
for(int i= ; i<l2 ; i++){
// if(node[LS(v2[i])].sz) cout<<"i: "<<i<<" "<<node[LS(v2[i])].sz<<endl;
c1+=node[LS(v2[i])].sz;
}
// cout<<"en: "<<l1<<" "<<l2<<" "<<o1<<" "<<o2<<" "<<c1<<" "<<l<<" "<<r<<" "<<k<<endl;
if(c1 >= k){
for(int i= ; i<l1 ; i++) v1[i] = LS(v1[i]);
for(int i= ; i<l2 ; i++) v2[i] = LS(v2[i]);
return query(v1 , v2 , LS(o1) , LS(o2) , l , m , k);
}else{
for(int i= ; i<l1 ; i++) v1[i] = RS(v1[i]);
for(int i= ; i<l2 ; i++) v2[i] = RS(v2[i]);
return query(v1 , v2 , RS(o1) , RS(o2) , m+ , r , k-c1);
}
} int query(int s , int t , int k)
{
v1.clear() , v2.clear();
int x = s-;
while(x>){
v1.push_back(T2[x]);
x-=lowbit(x);
}
x = t;
while(x>){
v2.push_back(T2[x]);
x-=lowbit(x);
}
return query(v1 , v2 , T1[s-] ,T1[t] , , n , k);
} char str[];
int cur[N]; int main()
{
//freopen("in.txt" , "r" , stdin);
//freopen("out1.txt" , "w" , stdout);
int T;
scanf("%d" , &T);
while(T--){
scanf("%d%d" , &n , &m);
tot = ;
for(int i= ; i<n ; i++){
scanf("%d" , val+i);
cur[i+] = val[i];
}
int cnt = n;
for(int i= ; i<m ; i++){
scanf("%s%d%d" , str , &s[i] , &t[i]);
if(str[] == 'Q'){
scanf("%d" , &rank[i]);
op[i] = ;
}
else{
op[i] = ;
val[cnt++] = t[i];
}
}
sort(val , val+cnt);
int pren = n;
n = unique(val , val+cnt)-val;
// cout<<pren<<" "<<n<<endl;
//初始建立静态主席树
T1[] = build( , n);
for(int i= ; i<=pren ; i++){
node[tot].init();
T1[i] = tot++;
build(T1[i-] , T1[i] , , n , Hash(cur[i]) , , i);
} memset(T2 , , sizeof(T2));
for(int i= ; i<m ; i++){
if(op[i]){
int pos = query(s[i] , t[i] , rank[i]);
printf("%d\n" , val[pos-]);
}else{
add(s[i] , Hash(cur[s[i]]) , -);
add(s[i] , Hash(t[i]) , );
cur[s[i]] = t[i];
}
}
}
return ;
}