块状物求调

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172#include<bits/stdc++.h>
using namespace std;

int n,q,m,x[70010],y[610];
struct X{
	int v[610],s[70010],sk[610];
	int pr,ne,l;
	int& operator [](const int x){
		return v[x];
	}
}a[610];
int block_size;
int get(int x){
	return x/300+1;
}
int qest(int l,int r,int k){
	int idl=1,idr=1;
	while(a[idl].l<l){
		l-=a[idl].l;
		idl=a[idl].ne;
	}
	while(a[idr].l<r){
		r-=a[idr].l;
		idr=a[idr].ne;
	}
	if(idl==idr){
		for(int i=l;i<=r;i++){
			x[a[idl][i]]++;
			y[get(a[idl][i])]++;
		}
		int tmp=0;
		while(y[tmp]<k){
			k-=y[tmp];
			tmp++;
		}
		tmp=(tmp-1)*300;
		while(x[tmp]<k){
			k-=x[tmp];
			tmp++;
		}
		for(int i=l;i<=r;i++){
			x[a[idl][i]]--;
			y[get(a[idl][i])]--;
		}
		return tmp;
	}
	for(int i=l;i<=a[idl].l;i++){
		x[a[idl][i]]++;
		y[get(a[idl][i])]++;
	}
	for(int i=1;i<=r;i++){
		x[a[idr][i]]++;
		y[get(a[idr][i])]++;
	}
	int tmp=0;
	while(a[a[idr].pr].sk[tmp]+y[tmp]-a[idl].sk[tmp]<k){
		k-=a[a[idr].pr].sk[tmp]+y[tmp]-a[idl].sk[tmp];
		tmp++;
	}
	tmp=(tmp-1)*300;
	while(a[a[idr].pr].s[tmp]+x[tmp]-a[idl].s[tmp]<k){
		k-=a[a[idr].pr].s[tmp]+x[tmp]-a[idl].s[tmp];
		tmp++;
	}
	for(int i=l;i<=a[idl].l;i++){
		x[a[idl][i]]--;
		y[get(a[idl][i])]--;
	}
	for(int i=1;i<=r;i++){
		x[a[idr][i]]--;
		y[get(a[idr][i])]--;
	}
	return tmp;
}
void change(int x,int v){
	int id=1;
	while(a[id].l<x){
		x-=a[id].l;
		id=a[id].ne;
	}
	int u=a[id][x];
	a[id][x]=v;
	while(id){
		a[id].s[u]--;
		a[id].s[v]++;
		a[id].sk[get(u)]--;
		a[id].sk[get(v)]++;
		id=a[id].ne;
	}
}
void split(int k){
	int l1=a[k].l/2;
	int l2=a[k].l-l1;
	m++;
	memcpy(a[m].s,a[k].s,sizeof(a[m].s));
	memcpy(a[m].sk,a[k].sk,sizeof(a[m].sk));
	for(int i=l1+1;i<=a[k].l;i++){
		a[m][i-l1]=a[k][i];
		a[k].s[a[k][i]]--;
		a[k].sk[get(a[k][i])]--;
	}
	a[k].l=l1;
	a[m].l=l2;
	a[a[k].ne].pr=m;
	a[m].ne=a[k].ne;
	a[k].ne=m;
	a[m].pr=k;
}
void insert(int x,int v){
	if(x==n+1){
		a[m][++a[m].l]=v;
		a[m].s[v]++;
		a[m].sk[get(v)]++;
		if(a[m].l>=600)split(m);
	}
	int id=1;
	while(a[id].l<x){
		x-=a[id].l;
		id=a[id].ne;
	}
	for(int i=a[id].l;i>=x;i--){
		a[id][i+1]=a[id][i];
	}
	a[id][x]=v;
	a[id].s[v]++;
	a[id].sk[get(v)]++;
	a[id].l++;
	while(id){
		a[id].s[v]++;
		a[id].sk[get(v)]++;
		id=a[id].ne;
	}
	if(a[id].l>=600)split(id);
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1,x,tmp;i<=n;i++){
		cin>>x;
		if(i%300==1){
			m++;
			memcpy(a[m].s,a[m-1].s,sizeof(a[m].s));
			memcpy(a[m].sk,a[m-1].sk,sizeof(a[m].sk));
			a[m-1].ne=m;
			a[m].pr=m-1;
			tmp=0;
		}
		a[m][++tmp]=x;
		a[m].l++;
		a[m].s[x]++;
		a[m].sk[get(x)]++;
	}
	cin>>q;
	char op;
	int l,r,v,ls=0;
	while(q--){
		cin>>op;
		if(op=='Q'){
			cin>>l>>r>>v;
			cout<<(ls=qest(l^ls,r^ls,v^ls))<<'\n';
		}
		else if(op=='M'){
			cin>>l>>v;
			change(l^ls,v^ls);
		}
		else{
			cin>>l>>v;
			insert(l^ls,v^ls);
		}
	}
    return 0;
}