我这 SGT+权值线段树 时间复杂度 $O(n \times log{n}^2)$ 就是被卡，这让我们人傻常数大的怎么活啊，或者有没有dalao帮忙卡卡常。

#include <bits/stdc++.h>
using namespace std;
#ifndef _GLIBCXX_IOMANIP
namespace std{
  struct _Setprecision { int _M_n; };
  inline _Setprecision
  setprecision(int __n)
  { return { __n }; }
}
#endif//_Setprecision
namespace fast_IO {
#define FASTIO
#define IOSIZE 100000
	long long preci=6;
	char ibuf[IOSIZE], obuf[IOSIZE];
	char *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#ifdef ONLINE_JUDGE
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#endif//fread in OJ, stdio in local
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33&&ch!=EOF)
	template<typename T> inline T read() {
		T s = 0;
		int w = 1;
		char ch;
		while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1;
		if (ch == EOF) return false;
		while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar();
		return s * w;
	}
	template<typename T> inline bool read(T &s) {
		s = 0;
		int w = 1;
		char ch;
		while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1;
		if (ch == EOF) return false;
		while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar();
		return s *= w, true;
	}
	inline bool read(char &s) {
		while (s = getchar(), isspace(s));
		return s!=EOF;
	}
	inline bool read(char *s) {
		char ch;
		while (ch = getchar(), isspace(ch));
		if (ch == EOF) return false;
		while (!isspace(ch)) *s++ = ch, ch = getchar();
		*s = '\000';
		return true;
	}
	inline bool read(bool &b){
		char ch;
		while(ch=getchar(),isspace(ch));
		if(ch==EOF)
			return false;
		b=ch^48;
		return true;
	}
	inline bool read(double &x){
		long long a = 0, b = 0, w = 0;
		char ch ;
		bool f = 0;
		while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') f = 1;
		if(ch==EOF)
			return false;
		while(isdigit(ch)){
			a =a*10 + ch-48;
			ch = getchar();
		}
		if(ch != '.'){
			x = (f ?-a :a);
			return 1;
		}
		ch = getchar();
		while(48<=ch && ch<=57){
			b = b*10 + ch-48;
			ch = getchar();
			w++;
		}
		x = b;
		while(w--)
			x /= 10;
		x = (f ?-a-x :a+x);
		return 1;
	}
	template<typename T> inline void print(T x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) print(x / 10);
		putchar(x % 10 + 48);
	}
	inline void print(char x) {
		putchar(x);
	}
	inline void print(char *x) {
		while (*x) putchar(*x++);
	}
	inline void print(const char *x) {
		for (int i = 0; x[i]; i++) putchar(x[i]);
	}
	inline void print(bool b){
		putchar(b+48);
	}
	inline void print(double x){
		long long xx,y=0,z,len=0;
		if(x<0) putchar('-'),x=-x;
		xx=x;
		x-=xx;
		for(int i=1; i<=preci; i++){
			x*=10;
			x+=1e-10;
			y=y*10+x;
			x-=(int)x;
		}
		x*=10;
		x+=1e-10;
		if(x>=5-1e-10){
			y++;
		}
		z=y;
		if(z==0)
			len=1;
		while(z){
			z/=10;
			len++;
		}
		if(preci<len){
			xx++;
			y=0;
			len=1;
		}
		print(xx);
		putchar('.');
		for(int i=1;i<=preci-len;i++)
			putchar('0');
		print(y);
	}
#ifdef _GLIBCXX_STRING
	inline bool read(std::string& s) {
		s = "";
		char ch;
		while (ch = getchar(), isspace(ch));
		if (ch == EOF) return false;
		while (!isspace(ch)) s += ch, ch = getchar();
		return true;
	}
	inline void print(std::string x) {
		for (int i = 0, n = x.size(); i < n; i++)
			putchar(x[i]);
	}
#endif//string
#ifdef _GLIBCXX_BITSET 
	template<size_t T> inline bool read(std::bitset<T>& x) {
		std::string s = "";
		char ch;
		while (ch = getchar(), isspace(ch));
		if (ch == EOF) return false;
		while (ch=='1'||ch=='0') s += ch, ch = getchar();
		x=std::bitset<T>(s);
		return true;
	}
	template<size_t T> inline void print(std::bitset<T> x) {
		print(x.to_string());
	}
#endif//bitset
	inline bool read(std::_Setprecision x) {
		preci=x._M_n;
		return true;
	}
	inline void print(std::_Setprecision x) {
		preci=x._M_n;
	}
#define FIO_EOF 0
#define FIO_OK 1
	template<typename T, typename... T1> inline bool read(T& a, T1&... other) {
		return read(a) && read(other...);
	}
	template<typename T, typename... T1> inline void print(T a, T1... other) {
		print(a);
		print(other...);
	}
	struct Fast_IO {
		Fast_IO() {
			eof=0;
		}
		~Fast_IO() {
			fwrite(obuf, p3 - obuf, 1, stdout);
		}
		bool eof;
		int precision(long long x=-1){
			if(x!=-1){
				long long old=preci;
				preci=x;
				return old;
			}
			return preci;
		}
		void merge_Fast_IO(bool eofed) {
			eof|=eofed;
		}
		operator bool(){
			return eof;
		}
	}io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) {
		return io.merge_Fast_IO(read(b)),io;
	}
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) {
		return print(b),io;
	}
#define cout io
#define cin io
#define endl '\n'
}
using namespace fast_IO;
// fast_IO ↑ 
const int maxn=1e7+10;
const int N=4e7+10;
int root;
int a[maxn],len;
int stk[maxn],top,cnt;
int n,m;
double alpha=0.8;
struct SGT{
	int ls,rs;
	int val;
	int root;
}sgt[maxn];
struct segment_tree{
	int ls,rs,s;
}seg[maxn];
int newnode(){
	int v=top?stk[top--]:++cnt;
	return v;
}
void delet(int &v){
	seg[v].s=0;
	if(!v)return ;
	stk[++top]=v;
	delet(seg[v].ls);
	delet(seg[v].rs);
	v=0;
}
void update(int &v,int l,int r,int x,int k){
	if(!v)v=newnode();
	seg[v].s+=k;
	if(!seg[v].s)return delet(v);
	if(l==r)return ;
	int mid=(l+r)>>1;
	if(x<=mid)update(seg[v].ls,l,mid,x,k);
	else update(seg[v].rs,mid+1,r,x,k);
}
void flatten(int v){
	if(!v)return ;
	flatten(sgt[v].ls);
	a[++len]=v;
	delet(sgt[v].root);
	flatten(sgt[v].rs);
}
int build(int l,int r){
	if(l>r)return 0;
	int mid=(l+r)>>1,v=a[mid];
	sgt[v].ls=build(l,mid-1);
	sgt[v].rs=build(mid+1,r);
	for(int i=l;i<=r;i++)update(sgt[v].root,0,N,sgt[a[i]].val,1);
	return v;
}
int rbu(int &v){
	len=0;
	flatten(v);
	v=build(1,len);
	return v;
}
bool check(int v){
	return ((alpha*seg[sgt[v].root].s)<=max(1.0*seg[sgt[sgt[v].ls].root].s,1.0*seg[sgt[sgt[v].rs].root].s));
}
void insert(int &v,int pos,int k){
	if(!v){
		v=++n;
		sgt[v].val=k;
		update(sgt[v].root,0,N,k,1);
		return ;
	}
	update(sgt[v].root,0,N,k,1);
	int sz=seg[sgt[sgt[v].ls].root].s;
	if(pos<=sz)insert(sgt[v].ls,pos,k);
	else insert(sgt[v].rs,pos-sz-1,k);
	if(check(v))v=rbu(v);
}
int modify(int v,int pos,int k){
	update(sgt[v].root,0,N,k,1);
	int sz=seg[sgt[sgt[v].ls].root].s;
	if(sz+1==pos){
		int val=sgt[v].val;
		sgt[v].val=k;
		update(sgt[v].root,0,N,val,-1);
		return val;
	}
	int val;
	if(pos<=sz)val=modify(sgt[v].ls,pos,k);
	else val=modify(sgt[v].rs,pos-sz-1,k);
	update(sgt[v].root,0,N,val,-1);
	return val;
}
int s[maxn],stop,p[maxn],ptop;
void find(int v,int x,int y){
	int ls=sgt[v].ls;
	int rs=sgt[v].rs;
	if(x==1&&y==seg[sgt[v].root].s){
		s[++stop]=sgt[v].root;
		return ; 
	}
	if(x<=seg[sgt[ls].root].s+1&&y>=seg[sgt[ls].root].s+1){
		p[++ptop]=v;
	}
	if(y<=seg[sgt[ls].root].s)find(ls,x,y);
	else if(x>seg[sgt[ls].root].s+1)find(rs,x-seg[sgt[ls].root].s-1,y-seg[sgt[ls].root].s-1);
	else{
		if(x<=seg[sgt[ls].root].s)find(ls,x,seg[sgt[ls].root].s);
		if(y>seg[sgt[ls].root].s+1)find(rs,1,y-seg[sgt[ls].root].s-1);
	}
}
int ask(int x,int y,int k){
	stop=ptop=0;
	find(root,x,y);
	int l=0,r=N;
	while(l<r){
		int mid=(l+r)>>1;
		int sum=0;
		for(int i=1;i<=stop;i++)sum+=seg[seg[s[i]].ls].s;
		for(int i=1;i<=ptop;i++){
			if(sgt[p[i]].val>=l&&sgt[p[i]].val<=mid)sum++;
		}
		if(sum<k){
			for(int i=1;i<=stop;i++)s[i]=seg[s[i]].rs;
			k-=sum,l=mid+1;
		}else{
			for(int i=1;i<=stop;i++)s[i]=seg[s[i]].ls;
			r=mid;
		}
	}
	return l;
}
void print(int v){
	if(!v)return ;
	cout<<sgt[v].val<<" "<<sgt[sgt[v].ls].val<<" "<<sgt[sgt[v].rs].val<<endl; 
	print(sgt[v].ls);
	print(sgt[v].rs);
}
int ans=0;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>sgt[i].val;
		sgt[i-1].rs=i;
	}
	sgt[0].rs=0;
	if(n)root=1,root=rbu(root);
	cin>>m;
	for(int i=1;i<=m;i++){
		char c;
		cin>>c;
		int pos,k;
		cin>>pos>>k;
		pos^=ans,k^=ans;
		if(c=='I'){
			insert(root,pos-1,k);
			//print(root);
		}else if(c=='M'){
			modify(root,pos,k);
		}else{
			int x;
			cin>>x;
			x^=ans;
			ans=ask(pos,k,x);
			cout<<ans<<endl;
		}
	}

	return 0;
}