rt

想不出来什么错的点了。

也许又是插入的锅？

#include<bits/stdc++.h>
using namespace std;
namespace fast_IO {
#define IOSIZE 100000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#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)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	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; }
	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 bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	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 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 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]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int 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() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return 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;
const int N=1e5+10;
const int C=350;
const int S=350;
struct Block
{
	vector<int> a;
	int lft=-1,rght=-1;
	int sums[N],sumc[C];
};
int n,m;
int limit=300,blo;
int bel[N],t[N];
int s[N],c[C],lst;
int T;
vector<Block> e;
Block tmp;
inline void init()
{
	bel[0]=1;for (int i=1;i<=1e5;i++) bel[i]=(i-1)/S+1;
	return ;
}
inline void split(int loc)
{
	tmp=e[loc];
	e.emplace_back(tmp);blo++;
	e[blo].lft=loc,e[blo].rght=e[loc].rght;
	if (e[loc].rght!=-1) e[e[loc].rght].lft=blo;
	e[loc].rght=blo;
	e[loc].a.erase(e[loc].a.begin()+limit,e[loc].a.end());
	e[e[loc].rght].a.erase(e[e[loc].rght].a.begin(),e[e[loc].rght].a.begin()+limit);
	for (auto v : e[e[loc].rght].a) e[loc].sums[v]--,e[loc].sumc[bel[v]]--;
	return ;
}
inline void emplace(int pos,int x)
{
	int loc=0;
	if (pos==m+1)
	{
		e[blo].a.emplace_back(x);
		loc=blo;
	}
	else
	{
		while (e[loc].a.size()<pos)
		{
			pos-=e[loc].a.size();
			loc=e[loc].rght;
			if (loc==-1) break;
		}
		pos--;
		e[loc].a.emplace(e[loc].a.begin()+pos,x);
	}
	for (int i=loc;i!=-1;i=e[i].rght) e[i].sums[x]++,e[i].sumc[bel[x]]++;
	if (e[loc].a.size()>(limit<<1)) split(loc);
	return ;
}
inline void update(int pos,int x)
{
	int loc=0;
	while (e[loc].a.size()<pos)
	{
		pos-=e[loc].a.size();
		loc=e[loc].rght;
		if (loc==-1) break;
	}
	pos--;
	int pst=e[loc].a[pos];
	e[loc].sums[pst]--,e[loc].sumc[bel[pst]]--;
	e[loc].sums[x]++,e[loc].sumc[bel[x]]++;
	e[loc].a[pos]=x;
	for (int i=e[loc].rght;i!=-1;i=e[i].rght) e[i].sums[pst]--,e[i].sumc[bel[pst]]--,e[i].sums[x]++,e[i].sumc[bel[x]]++;
	return ;
}
inline int query(int l,int r,int k)
{
	int bll=0;
	while (e[bll].a.size()<l)
	{
		l-=e[bll].a.size();
		bll=e[bll].rght;
		if (bll==-1) break;
	}
	l--;
	int blr=0;
	while (e[blr].a.size()<r)
	{
		r-=e[blr].a.size();
		blr=e[blr].rght;
		if (blr==-1) break;
	}
	r--;
	if (bll==blr)
	{
		for (int i=l;i<=r;i++) s[e[bll].a[i]]++,c[bel[e[bll].a[i]]]++;
		int siz=0,ll,rr;
		for (int i=1;i<=C;i++)
		{
			siz+=c[i];
			if (siz>=k)
			{
				siz-=c[i];
				ll=(i-1)*S+1;
				if (i==1) ll=0;
				rr=i*S;
				break;
			}
		}
		int ans=0;
		for (int i=ll;i<=rr;i++)
		{
			siz+=s[i];
			if (siz>=k)
			{
				ans=i;
				break;
			}
		}
		for (int i=l;i<=r;i++) s[e[bll].a[i]]--,c[bel[e[bll].a[i]]]--;
		return ans;
	}
	if (e[blr].lft==-1) exit(0);
	for (int i=l;i<e[bll].a.size();i++) s[e[bll].a[i]]++,c[bel[e[bll].a[i]]]++;
	for (int i=0;i<=r;i++) s[e[blr].a[i]]++,c[bel[e[blr].a[i]]]++;
	int siz=0,ll,rr;
	for (int i=1;i<=C;i++)
	{
		siz+=(c[i]+e[e[blr].lft].sumc[i]-e[bll].sumc[i]);
		if (siz>=k)
		{
			siz-=(c[i]+e[e[blr].lft].sumc[i]-e[bll].sumc[i]);
			ll=(i-1)*S+1;
			if (i==1) ll=0;
			rr=i*S;
			break;
		}
	}
	int ans=0;
	for (int i=ll;i<=rr;i++)
	{
		siz+=(s[i]+e[e[blr].lft].sums[i]-e[bll].sums[i]);
		if (siz>=k)
		{
			ans=i;
			break;
		}
	}
	for (int i=l;i<e[bll].a.size();i++) s[e[bll].a[i]]--,c[bel[e[bll].a[i]]]--;
	for (int i=0;i<=r;i++) s[e[blr].a[i]]--,c[bel[e[blr].a[i]]]--;
	return ans;
}
inline void calc()
{
	e.emplace_back();
	for (int i=1;i<=n;i++)
	{
		e[blo].a.emplace_back(t[i]);
		e[blo].sums[t[i]]++;
		e[blo].sumc[bel[t[i]]]++;
		if (e[blo].a.size()>(limit<<1)) split(blo);
	}
	m=n;
	return ;
}
signed main()
{
	init();
	cin>>n;
	for (int i=1;i<=n;i++) cin>>t[i];
	calc();
	cin>>T;
	while (T--)
	{
		char op;int x,val,l,r,k;
		cin>>op;
		if (op=='Q')
		{
			cin>>l>>r>>k;
			l^=lst,r^=lst,k^=lst;
			lst=query(l,r,k);
			cout<<lst<<endl;
		}
		if (op=='M')
		{
			cin>>x>>val;
			x^=lst,val^=lst;
			update(x,val);
		}
		if (op=='I')
		{
			cin>>x>>val;
			x^=lst,val^=lst;
			emplace(x,val);
			m++;
		}
	}
	return (0-0);
}