实在调不动了……整体思路马蜂都和第一篇题解很像（好像只有离散化不一样。。但是我测了好像没问题）

#include <bits/stdc++.h>
using namespace std;
#define rep(a,b,c) for(int a=b;a<=c;a++)
int lowbit(int x){return x& -x;}
const int N=6e5+5;
struct note 
{
	int ls,rs,num;//左儿子，右儿子，节点值 
};
note t[N<<8];int top=0;int a[N];
int root[N];int n,m;
//对主席树更新 
void modify(int &ss,int l,int r,int k,int val)//ss为当前节点，l,r左界右界 ，k目标数,val改变值 
{
	//cout<<l<<" "<<r<<" "<<k<<endl;
	if(!ss)	ss=++top;
	t[ss].num+=val;
	if(l==r) return;
	int mid=(l+r)>>1;
	if(k<=mid) modify(t[ss].ls,l,mid,k,val);
	else modify(t[ss].rs,mid+1,r,k,val);
}
void Modify(int k,int val)//在树状数组上更新 
{
	int x=k; 
	while(x<=n)
	{
		modify(root[x],1,n+m,a[k],val);//更新主席树 
		x+=lowbit(x);
	}
}
int se[N][2];int cnt[2];//se为节点列表，cnt为节点个数 
void move_r(){for(int p=0;p<=1;p++) for(int i=1;i<=cnt[p];i++) se[i][p]=t[se[i][p]].rs;}//log个节点全部跳到右儿子 
void move_l(){for(int p=0;p<=1;p++) for(int i=1;i<=cnt[p];i++) se[i][p]=t[se[i][p]].ls;}//log个节点全部挑到左儿子 
int rul(){int sum=0;for(int i=1;i<=cnt[1];i++) sum+=t[t[se[i][1]].ls].num;for(int i=1;i<=cnt[0];i++) sum-=t[t[se[i][0]].ls].num;return sum;}
//查询log个节点的左节点值
int query(int l,int r,int k)//查询主席树 
{
	if(l==r) return l;
	int mid=(l+r)>>1;
//	cout<<l<<" "<<r<<" "<<rul()<<" "<<k<<endl;
	int sum=rul();
	if(k<=sum){move_l();query(l,mid,k);}
	else {move_r();query(mid+1,r,k-sum);}
}
int Query(int l,int r,int k)//查询树状数组 
{
	memset(se,0,sizeof(se));cnt[1]=cnt[0]=0;
	while(l){se[++cnt[0]][0]=root[l];l-=lowbit(l);}//找出树状数组维护的需要查询的主席树的根节点 
	while(r){se[++cnt[1]][1]=root[r];r-=lowbit(r);}//同上 
	return query(1,n+m,k);
}
pair<int,int> r[N];int re[N];//r为离散化数组，first存原值,second存位置 
void lsh()//离散化到a数组 
{
	sort(r+1,r+1+n+m);int las=0;
	r[0].first=-1;
	for(int i=1;i<=n+m;i++)
	{
		if(r[i].first!=r[i-1].first) las++;
		a[r[i].second]=las;re[las]=r[i].first;
	}
}
struct getin
{
	int l,r,k;
	char kin;
};getin ri[N];//存操作 
int main()
{
	freopen("P2617_1.in","r",stdin);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>r[i].first; r[i].second=i;
	}
	 int l,rr,k;char kin;
	 for(int i=1;i<=m;i++)//离线存储询问，将询问中新加的数添加到r数组之后以便对所有数进行离散化 
	 {
	 	cin>>kin;
	 	if(kin=='Q')
		{
			cin>>l>>rr>>k;
			r[i+n]=make_pair(0x3f3f3f3f,i+n);//通过极值屏蔽掉询问,保证离散化后的数组最小值为1（虽然好像没必要） 
		}
		else 
		{
			cin>>l>>k;
			r[i+n]=make_pair(k,i+n);//k为原始值，i+n表示第i个询问，保证离散化后值还能查到 
	 	}
	 	ri[i]=getin{l,rr,k,kin};//把操作离线下来 
	 }
	lsh();
	for(int i=1;i<=n;i++) Modify(i,1);//添加初始数组到主席树 
	//rep(i,0,n+m) cout<<a[i]<<" ";cout<<endl;
	//rep(i,1,n+m) cout<<r[i].first<<" "<<r[i].second<<"\n";cout<<endl;
	for(int i=1;i<=m;i++)
	{
		
		if(ri[i].kin=='Q') cout<<re[Query(ri[i].l-1,ri[i].r,ri[i].k)]<<"\n";//re为还原数组（将离散化后的值还原为离散化之前的） 
		else 
		{
			Modify(ri[i].l,-1);//删除原值 
			a[ri[i].l]=a[n+i];//更改 
			Modify(l,1);//添加 
		}
	//	cout<<i<<"****\n";
	//	rep(j,1,n) cout<<a[j]<<" ";cout<<endl;
	//	cout<<"qs";rep(i,1,n) cout<<Query(0,n,i)<<" ";cout<<endl;
	}
	return 0;
}