题意：
在静态主席树的基础上，增加修改。
题解：
===在写
#include<bits/stdc++.h>using namespace std;const int maxn = 60009;
int a[maxn],sor[maxn];
int tree1[maxn],tree2[maxn],lson[maxn<<5],rson[maxn<<5],sum[maxn<<5];int n,m,cnt;struct node
{int l,r,k;int q;
}op[10005];int build(int l,int r)
{int rt = (++cnt);sum[rt] = 0;if(l!=r){int m = (l+r)>>1;lson[rt] = build(l,m);rson[rt] = build(m+1,r);}return rt;
}int update(int pre,int l, int r,int x,int v)
{int rt = ++cnt;lson[rt] = lson[pre],rson[rt] = rson[pre],sum[rt] = sum[pre] + v;if(l<r){int m = (l+r)>>1;if(x<=m)lson[rt] = update(lson[pre],l,m,x,v);else rson[rt] = update(rson[pre],m+1,r,x,v);}return rt;
}int lowbit(int x)
{return x&-x;
}int next[maxn];
void add(int x,int pos,int v)
{while(x<=n){tree2[x] = update(tree2[x],1,m,pos,v);x+=lowbit(x);}
}
int getsum(int x)
{int res = 0;while(x>0){res += sum[lson[next[x]]];x-=lowbit(x);}return res;
}int query(int u,int v,int rl,int rr,int l,int r,int k)
{if(l>=r)return l;int m = (l+r)>>1;int tmp = getsum(v) - getsum(u) + sum[lson[rr]] - sum[lson[rl]];//tree2+tree1if(tmp>=k){for(int i = u;i;i-=lowbit(i))next[i] = lson[next[i]];for(int i = v;i;i-=lowbit(i))next[i] = lson[next[i]];return query(u,v,lson[rl],lson[rr],l,m,k);}else{for(int i = u;i;i-=lowbit(i))next[i] = rson[next[i]];for(int i=v;i;i-=lowbit(i))next[i] = rson[next[i]];return query(u,v,rson[rl],rson[rr],m+1,r,k-tmp);}
}int main()
{int t;cin>>t;while(t--){int q;scanf("%d%d",&n,&q);cnt = 0;m=0;for(int i=1;i<=n;i++){scanf("%d",a+i);sor[++m] = a[i];}for(int i=0;i<q;i++){char s[10];scanf("%s",s);if(s[0]=='Q'){scanf("%d%d%d",&op[i].l,&op[i].r,&op[i].k);op[i].q = 1;}else{scanf("%d%d",&op[i].l,&op[i].r);op[i].q=0;sor[++m]=op[i].r;}}sort(sor+1,sor+1+m);m = unique(sor+1,sor+1+m) - sor-1;tree1[0] = build(1,m);for(int i = 1;i<=n;i++)tree1[i] = update(tree1[i-1],1,m,lower_bound(sor+1,sor+1+m,a[i])-sor,1);for(int i=1;i<=n;i++)tree2[i] = tree1[0];for(int i=0;i<q;i++){if(op[i].q){for(int j=op[i].l-1;j;j-=lowbit(j))next[j] = tree2[j];for(int j=op[i].r;j;j-=lowbit(j))next[j] = tree2[j];printf("%d\n",sor[query(op[i].l-1,op[i].r,tree1[op[i].l-1],tree1[op[i].r],1,m,op[i].k)] );}else{add(op[i].l,lower_bound(sor+1,sor+1+m,a[op[i].l])-sor,-1);add(op[i].l,lower_bound(sor+1,sor+1+m,op[i].r)-sor,1);a[op[i].l] = op[i].r;}}}return 0;
}