这不是题解，不属于在讨论区中发题解。 这题以前时限1秒，绝大多数正常写法均无法通过，后来时限改为2秒，才能够让正常根号写法和原来想卡的根号写法一起通过。但暴力即可在1s内通过。即去掉占常数大头的块状链表，暴力在所属块内插入，没有分裂大块，然后就变成了简单好写的P2617 但这样复杂度显然错完了，因为可能会导致一个块特别大，插入和查询复杂度每次都到达线性。 AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define fi first
#define se second
typedef double db;
#define pb push_back
#define eb emplace_back
#define bcnt __builtin_popcount
#define TS printf("!!!tiaoshi\n")
const int inf=1e9+7;
const int N=1e5+5;
const int M=335;
int n,m,cnt,mx=70001,a[N],b[M],sz[M],bel[N],ax[M][M],ay[M][N],bx[M];
int k,sum,num[M][M*50];
inline void add(int x,int y,int k){
	for(;x<=cnt;x++) ax[x][bel[y]]+=k,ay[x][y]+=k;
}
void init(){
	k=sqrt(mx),sum=(mx-1)/k+1;
	for(int i=1;i<=mx;i++) bel[i]=(i-1)/k+1;
	k=sqrt(n);
	int la=1,nw=0;
	while(nw<n){
		nw=min(nw+k,n),cnt++;
		for(int i=la;i<=nw;i++) num[cnt][++sz[cnt]]=a[i];
		la=nw+1; 
	}
	for(int i=1;i<=cnt;i++){
		for(int j=1;j<=sz[i];j++) add(i,num[i][j],1);
	}k=sqrt(mx);
}
void out(){
	printf("init:%d %d %d\n",k,cnt,n);
	for(int i=1;i<=cnt;i++){
		printf("block:%d\n",i);
		for(int j=1;j<=sz[i];j++) printf("%d ",num[i][j]-1);puts("");
	}
}
inline pii find(int x){
	int bl=1,nw=0;
	while(nw+sz[bl]<x) nw+=sz[bl],bl++;
	return {bl,x-nw};
}
inline void get(int bl,int l,int r,int x){
	int y=(x-1)*k;
	for(int i=l;i<=r;i++){
		int z=num[bl][i],bz=bel[z];
		if(!x) bx[bz]++;
		else if(bz==x) bx[z-y]++;
	}
}
int qiu(int l,int r,int x){
	pii nl=find(l),nr=find(r);
	int bl=nl.fi,br=nr.fi,li=nl.se,ri=nr.se;
	if(bl==br) get(bl,li,ri,0);	
	else{
		get(bl,li,sz[bl],0),get(br,1,ri,0);
		for(int i=1;i<=sum;i++) bx[i]+=ax[br-1][i]-ax[bl][i];
	}
	int nw=1,tot=0,bj;
	while(tot+bx[nw]<x) tot+=bx[nw],nw++;
	x-=tot,bj=nw;
	int lim=(bj-1)*k;
	memset(bx,0,sizeof(bx));
	if(bl==br) get(bl,li,ri,bj);	
	else{
		get(bl,li,sz[bl],bj),get(br,1,ri,bj);
		for(int i=lim+1;i<=lim+k;i++) bx[i-lim]+=ay[br-1][i]-ay[bl][i];
	}
	nw=1;
	while(bx[nw]<x) x-=bx[nw],nw++;
	memset(bx,0,sizeof(bx));
	return nw+lim-1;  
}
inline void ins(int x,int y){
	if(x==n+1){
		add(cnt,y,1),n++;
		num[cnt][++sz[cnt]]=y;
		return;
	}
	pii nw=find(x);
	int bl=nw.fi,wz=nw.se;
	add(bl,y,1);
	for(int i=sz[bl];i>=wz;i--) num[bl][i+1]=num[bl][i];
	num[bl][wz]=y,sz[bl]++,n++;
}
inline void upd(int x,int y){
	pii nw=find(x);
	int bl=nw.fi,wz=nw.se;
	add(bl,num[bl][wz],-1),add(bl,y,1),num[bl][wz]=y;
}
int q;
#define gc getchar
inline int read(){
	int x=0;char ch=gc();
	while(ch<'0'||ch>'9') ch=gc();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gc();
	return x;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) a[i]=read()+1;
	init();
	scanf("%d",&q);
	char op[5];int l,r,x,lastans=0; 
	for(int i=1;i<=q;i++){
		scanf("%s",op+1);
		l=read(),r=read();
		l^=lastans,r^=lastans;
		if(op[1]=='Q'){
			scanf("%d",&x);x^=lastans;
			lastans=qiu(l,r,x);
			printf("%d\n",lastans);
		}else if(op[1]=='M') upd(l,r+1);
		else ins(l,r+1);
		//out();
	}
	return 0;
}