自认为马蜂良好，常数不大(失误写成$log^3n$了，也能过吧)

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
mt19937 g(random_device{}());
struct{
	int l,r,val,siz,pri;//BigRoot
}tr[N*17];
int tol;
inline int newnode(int val){
	tr[++tol].pri=g();
	tr[tol].val=val;
	return tol;
}
inline void update(int i){
	tr[i].siz=tr[tr[i].l].siz+tr[tr[i].r].siz+1;
}
void split(int i,int val,int&L,int&R){
	if(!i){L=R=0;return;}
	if(tr[i].val<=val)L=i,split(tr[i].r,val,tr[i].r,R);
	else R=i,split(tr[i].l,val,L,tr[i].l);
	update(i);
}
int merge(int L,int R){
	if(!L||!R)return L+R;
	if(tr[L].pri<=tr[R].pri){
		tr[R].l=merge(L,tr[R].l);
		update(R);return R;
	}else{
		tr[L].r=merge(tr[L].r,R);
		update(L);return L;
	}
}
void insert(int&root,int i){
	int L,R,p;
	split(root,tr[i].val-1,L,R);
	split(L,tr[i].val,p,R);
	p=merge(p,i);R=merge(p,R);root=merge(L,R);
}
int se[N<<2],a[N];
inline int ls(int i){return i<<1;}
inline int rs(int i){return i<<1|1;}
int query(int i,int l,int r,int ql,int qr,int x){
	if(ql<=l&&r<=qr){
		int L,R,res;
		split(se[i],x-1,L,R);
		res=tr[L].siz;
		merge(L,R);
		return res;
	}
	int mid=(l+r)>>1,res=0;
	if(ql<=mid)res+=query(ls(i),l,mid,ql,qr,x);
	if(mid<qr)res+=query(rs(i),mid+1,r,ql,qr,x);
	return res;
}
void change(int i,int l,int r,int x,int y){//a_x->y
	if(l==r){
		tr[se[i]].val=y;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)change(ls(i),l,mid,x,y);
	else change(rs(i),mid+1,r,x,y);
	int L,R,p;
	split(se[i],a[x]-1,L,R);
	split(R,a[x],p,R);
	int o=p;tr[o].val=y;
	p=merge(tr[p].l,tr[p].r);
	L=merge(L,p);se[i]=merge(L,R);
	insert(se[i],o);
}
void build(int i,int l,int r){
	if(l==r){
		se[i]=newnode(a[l]);
		return;
	}
	int mid=(l+r)>>1;
	build(ls(i),l,mid);
	build(rs(i),mid+1,r);
	for(int j=l;j<=r;j++)insert(se[i],newnode(a[j]));
}
int main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0),cout.tie(0);
	int n,m;cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	while(m--){
		char ch;cin>>ch;
		if(ch=='Q'){
			int L,R,k;
			cin>>L>>R>>k;
			k--;//k-1个数严格小于ans 
			int l=0,r=1e9+5;
			while(l<r){
				int mid=(l+r+1)>>1;
				if(query(1,1,n,L,R,mid)<=k)l=mid;
				else r=mid-1;
			}
			cout<<l<<"\n"; 
		}else{
			int x,y;cin>>x>>y;
			change(1,1,n,x,y);
			a[x]=y;
		}
	}
	return 0;
}