现在把主席树的原理给弄清楚了，从i=1开始，每次新插入一个数，就为他建一棵线段树（当然第一次i=0的时候是建一棵空树），线段树里面保存的是1-i的树的位置情况
简单来说，如果有m个树，则每棵线段树都是范围为1-m的，至于1-i没有m个那就先让它空着不管，我只负责1-i里面的数的位置情况插入到线段树里面，左孩子是大小k<=size/2的，右孩子是k>size的，size是线段树的深入层次而定，一开始就是m的，而不用每次都为1-i每个树插入值（不仅耗时，空间也耗不起），我只考虑当前这个Ai，至于1到i-1，已经在T[i-1]里面存了，我如果当前孩子是往左走的，那我复用T[i-1]的右孩子即可，反过来也是一样的，这样，每次建树 最多logN，最多也只建了logN个节点，所有总节点数目为N*logN，在N为不超过千万的范围内，是可以承受的。。。不过这道题为什么要*40才能过。。我也没搞清，好像觉得不用开这么大，但我试了下不开久会WA。
因为主席树每颗线段树结构相同并且还高度复用，所以他的一个很奇妙的特性就是他支持加减操作，一般就是用他的减操作，要求区间A到B的，则用T[j] 和T[i-1]的左支相减即可得到当前这个区间里线段树左边存的是多大的，右边存的是多大的，用pos代进去即可，往左走 往右走，把整个二分走完即可得到答案
树状数组套线段树我暂时还没完全弄清，反正为了记录修改，每次都像之前插入值一样新开了树，而且要用离线，把要修改的那些值预先存进去
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N =60000+10;
const int maxn=N*40;
int tot;
int T[N],A[N],t[N],s[N];
int lson[maxn],rson[maxn],c[maxn];
int used[N];
int n,q,m;
struct node
{
int kind,l,r,k;
}Q[10010];
void init()
{
sort(t+1,t+1+m);
m=unique(t+1,t+1+m)-t-1;
}
int build(int l,int r)
{
int rt=tot++;
c[rt]=0;
if (l>=r) return rt;
int mid=(l+r)>>1;
lson[rt]=build(l,mid);
rson[rt]=build(mid+1,r);
return rt;
}
int lowbit(int x)
{
return x&(-x);
}
int sum(int x)
{
int ret=0;
while (x>0)
{
ret+=c[lson[used[x]]];
x-=lowbit(x);
}
return ret;
}
int query(int L,int R,int k)
{
int lrt=T[L-1];
int rrt=T[R];
int l=1,r=m;
for (int i=L-1;i;i-=lowbit(i)){
used[i]=s[i];
}
for (int i=R;i;i-=lowbit(i)){
used[i]=s[i];
}
while (l<r)
{
int mid=(l+r)>>1;
int tmp=sum(R)-sum(L-1)+c[lson[rrt]]-c[lson[lrt]];
if (tmp>=k){
r=mid;
for (int i=L-1;i;i-=lowbit(i)){
used[i]=lson[used[i]];
}
for (int i=R;i;i-=lowbit(i)){
used[i]=lson[used[i]];
}
lrt=lson[lrt];
rrt=lson[rrt];
}
else{
l=mid+1;
k-=tmp;
for (int i=L-1;i;i-=lowbit(i)){
used[i]=rson[used[i]];
}
for (int i=R;i;i-=lowbit(i)){
used[i]=rson[used[i]];
}
lrt=rson[lrt];
rrt=rson[rrt];
}
}
return l;
}
int inserts(int rt,int pos,int val)
{
int newrt=tot++,tmp=newrt;
int l=1,r=m;
c[newrt]=c[rt]+val;
while (l<r)
{
int mid=(l+r)>>1;
if (pos<=mid){
lson[newrt]=tot++;
rson[newrt]=rson[rt];
rt=lson[rt];
newrt=lson[newrt];
r=mid;
}
else{
rson[newrt]=tot++;
lson[newrt]=lson[rt];
rt=rson[rt];
newrt=rson[newrt];
l=mid+1;
}
c[newrt]=c[rt]+val;
}
return tmp;
}
void add(int loc,int p,int val)
{
while (loc<=n)
{
s[loc]=inserts(s[loc],p,val);
loc+=lowbit(loc);
}
}
int main()
{
char op[5];
int kase,a,b,k;
scanf("%d",&kase);
while (kase--)
{
tot=0;
scanf("%d%d",&n,&q);
for (int i=1;i<=n;i++) scanf("%d",&A[i]),t[i]=A[i];
m=n;
for (int i=0;i<q;i++){
scanf("%s",op);
if (op[0]=='Q'){
scanf("%d%d%d",&a,&b,&k);
Q[i]=(node){0,a,b,k};
}
else{
scanf("%d%d",&a,&b);
Q[i]=(node){1,a,b,0};
t[++m]=b;
}
}
init();
T[0]=build(1,m);
for (int i=1;i<=n;i++){
int pos=lower_bound(t+1,t+m+1,A[i])-t;
T[i]=inserts(T[i-1],pos,1);
}
for (int i=0;i<=n;i++) s[i]=T[0];
for (int i=0;i<q;i++)
{
int a,b,k;
if (Q[i].kind==0){
a=Q[i].l;b=Q[i].r;k=Q[i].k;
int ans=query(a,b,k);
printf("%d
",t[ans]);
}
else{
a=Q[i].l;
b=Q[i].r;
int pos;
pos=lower_bound(t+1,t+1+m,A[a])-t;
add(a,pos,-1);
pos=lower_bound(t+1,t+1+m,b)-t;
add(a,pos,1);
A[a]=b;
}
}
}
return 0;
}