Bzoj 1901 Zju2112 Dynamic Rankings（树状数组+主席树） (三)
t i=left-1;i;i-=lowbit(i)) use[i]=T[i];
for(int i=right;i;i-=lowbit(i)) use[i]=T[i];
while(l
int mid=(l+r)>>1;
int tmp=sum(right)-sum(left-1);
if(tmp>=k){
r=mid;
for(int i=left-1;i;i-=lowbit(i))
use[i]=lson[use[i]];
for(int i=right;i;i-=lowbit(i))
use[i]=lson[use[i]];
}
else{
l=mid+1;
k-=tmp;
for(int i=left-1;i;i-=lowbit(i))
use[i]=rson[use[i]];
for(int i=right;i;i-=lowbit(i))
use[i]=rson[use[i]];
}
}
return l;
}
void Init_tree(){
T[0]=bulid(0,m-1);
//所有位置初始为空树
for(int i=1;i<=n;i++)
T[i]=T[0];
//更新所有位置
for(int i=1;i<=n;i++)
add(i,hash(a[i]),1);
}
int main(){
int t=1;
scanf("%d",&t);
while(t--){
tot=0;m=0;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
h[m++]=a[i];
}
for(int i=0;i
char str[5];int l,r,k;
scanf("%s",str);
if(str[0]=='Q'){
scanf("%d%d%d",&l,&r,&k);
Q[i]=Question(0,l,r,k);
}
else{
scanf("%d%d",&l,&k);
Q[i]=Question(1,l,0,k);
h[m++]=k;
}
}
Init_hash(m);
Init_tree();
for(int i=0;i
if(Q[i].kind==0){
printf("%d\n",h[query(Q[i].l,Q[i].r,Q[i].k)]);
}
else{
add(Q[i].l,hash(a[Q[i].l]),-1);
add(Q[i].l,hash(Q[i].k),1);
a[Q[i].l]=Q[i].k;
}
}
}
return 0;
}