RT。用的块状链表，本地用时 4.5s 左右。

#include<bits/stdc++.h>
#define N 70000
#define S 1600
using namespace std;
struct kzlb{
	int nm,sz[2*S+5],nxt[2*S+5],a[2*S+5][S+5],srt[2*S+5][S+5];
	inline void debug()
	{
		cout<<"--------------------------\n";
		for(int i=1;i<=nm;i++)
		{
			cout<<"[ ";
			for(int j=1;j<=sz[i];j++) cout<<a[i][j]<<' ';
			cout<<"]\n{ ";
			for(int j=1;j<=sz[i];j++) cout<<srt[i][j]<<' ';
			cout<<"}\n";
		}
	}
	inline void init(int x)
	{
		nm=1;
		memset(sz,0,sizeof(sz));sz[1]=1;
		memset(a,0,sizeof(a));a[1][1]=x;
		memset(srt,0,sizeof(srt));srt[1][1]=x;
	}
	inline void resort(int x)
	{
		for(int i=1;i<=sz[x];i++)
			srt[x][i]=a[x][i];
		sort(srt[x]+1,srt[x]+1+sz[x]);
	}
	inline void split(int x)
	{
		nm++;
		for(int i=S/2+1;i<=sz[x];i++)
			a[nm][i-S/2]=a[x][i];
		sz[nm]=sz[x]-S/2;
		sz[x]=S/2;
		nxt[nm]=nxt[x];
		nxt[x]=nm;
		resort(x),resort(nm);
	}
	inline void insert(int x,int y,int z)//insert y to block x,z's right
	{
		for(int i=sz[x];i>=z+1;i--) a[x][i+1]=a[x][i];
		a[x][z+1]=y;
		sz[x]++;
		if(sz[x]>S) split(x);
		else
		{
			for(int i=1;i<=sz[x]-1;i++)
				if(srt[x][i]>y) swap(srt[x][i],y);
			srt[x][sz[x]]=y;
		}
	}
	inline int find(int &x)
	{
		int nh=1;
		while(x-sz[nh]>0) x-=sz[nh],nh=nxt[nh];
		return nh;
	}
	inline void insert(int x,int y)//insert y to x's right
	{int nh=find(x);insert(nh,y,x);}
	inline void update(int x,int y)
	{
		int nh=find(x);
		a[nh][x]=y;
		int pos=x;
		while(pos<sz[nh]&&y<srt[nh][pos+1])
			pos++,swap(y,srt[nh][pos]);
		while(pos>1&&y>srt[nh][pos-1])
			pos--,swap(y,srt[nh][pos]);
	}
	inline int cntsmaller(int x,int y,int z,int t)
	{
		if(y==1&&z==sz[x])//when testing,only use brute force,comment binary search
		{
			int l=0,r=sz[x]+1;
			while(r-l>1)
			{
				int mid=(l+r)/2;
				if(a[x][mid]<=t) l=mid;
				else r=mid;
			}
			return l;
		}
		else
		{
			int res=0;
			for(int i=y;i<=z;i++)
				if(a[x][i]<=t) res++;
			return res;
		}
	}
	inline int check(int x,int y,int z,int nhx,int nhy)
	{
		int res=0;
		if(nhx==nhy) return cntsmaller(nhx,x,y,z);
		else
		{
			int res=cntsmaller(nhx,x,sz[nhx],z);
			res+=cntsmaller(nhy,1,y,z);
			for(int i=nhx+1;i<=nhy-1;i++)
				res+=cntsmaller(i,1,sz[i],z);
			return res;
		}
	}
	inline int query(int x,int y,int z)
	{
		int l=-1,r=70001,nhx=find(x),nhy=find(y);
		while(r-l>1)
		{
			int mid=(l+r)/2;
			if(check(x,y,mid-1,nhx,nhy)<z) l=mid;
			else r=mid;
		}
		return l;
	}
};
kzlb a;
int n,q,la;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		if(i==1) a.init(x);
		else a.insert(i-1,x);
	//	a.debug();
	}
	cin>>q;
	while(q--)
	{
		int l,r,c;
		string opt;
		cin>>opt;
		scanf("%d%d",&l,&r);
		l^=la,r^=la;
		if(opt[0]=='I')
			a.insert(l-1,r);
		else if(opt[0]=='M')
			a.update(l,r);
		else
			scanf("%d",&c),
			c^=la,
			printf("%d\n",la=a.query(l,r,c));
	//	a.debug();
	}
	return 0;
}