是块状链表的写法，调了半天了，BallBall大佬们帮我看看。

#include<cstdio>
#include<cctype>
#include<cstring>
#include<cassert>
#include<algorithm>
#define bev(x) ((x-1)/lv+1)
#define L(x) ((x-1)*lv+1)
#define R(x) (x*lv)
using namespace std;
const int lv=300;
const int ls=200;
const int maxn=700010;
int in(){
	int v=0;char c='~';
	while(!isdigit(c))c=getchar();
	while( isdigit(c))v=v*10+c-'0',c=getchar();
	return v;
}
int getaph(){
	char c='^';
	while(!isalpha(c))c=getchar();
	return c;
}
struct node{
	int v[810];
	int s[70010];
	int o[810];
	int cnt;
	int nxt;
}c[810];
int v[810],s[maxn],h=1;
struct ret{int b,p;};
ret getpos(int x){
	ret rt=(ret){1,0};
	while((c[rt.b].nxt>0)&&c[rt.b].cnt<x){
		x-=c[rt.b].cnt;
		rt.b=c[rt.b].nxt;
	}
	rt.p=x;
	return rt;
}
int findk(int apl,int apr,int k){
	int rt=-1;
	for(int i=1;i<=300;i++){
		if(v[i]+c[apr].v[i]-c[apl].v[i]<k){
			k-=v[i]+c[apr].v[i]-c[apl].v[i];
			continue;
		}
		for(int j=L(i);j<=R(i);j++){
			if(s[j]+c[apr].s[j]-c[apl].s[j]<k)
				k-=s[j]+c[apr].s[j]-c[apl].s[j];
			else {rt=j;return rt;}
		}
	}
	return -1;
}
void check(){
	for(int i=1;i<=400;i++)assert(!v[i]);
}

int query(int l,int r,int k){
	if(l>r)swap(l,r);
	ret pl=getpos(l);
	ret pr=getpos(r);
	if(pl.b==pr.b){
		int B=pl.b;
		for(int i=pl.p;i<=pr.p;i++){
			s[c[B].o[i]]++;
			v[bev(c[B].o[i])]++;
		}
		int ret=findk(0,0,k);
		for(int i=pl.p;i<=pr.p;i++){
			s[c[B].o[i]]--;
			v[bev(c[B].o[i])]--;
		}
		check();
		return ret;
	}
	int dx=1,ret=0;
	for(int i=pl.p;i<=c[pl.b].cnt;i++){
		s[c[pl.b].o[i]]+=dx;
		v[bev(c[pl.b].o[i])]+=dx;
	}
	for(int i=pr.p;i>=1;i--){
		s[c[pr.b].o[i]]+=dx;
		v[bev(c[pr.b].o[i])]+=dx;
	}
	ret=findk(pl.b,pr.b-1,k);
	dx=-1;
	for(int i=pl.p;i<=c[pl.b].cnt;i++){
		s[c[pl.b].o[i]]+=dx;
		v[bev(c[pl.b].o[i])]+=dx;
	}
	for(int i=pr.p;i>=1;i--){
		s[c[pr.b].o[i]]+=dx;
		v[bev(c[pr.b].o[i])]+=dx;
	}
	check();
	return ret;
}
void split(int x){
	//puts("split");
	int siz=c[x].cnt>>1;
	c[++h]=c[x];
	c[h].cnt=0;
	for(int i=siz+1;i<=c[x].cnt;i++){
		c[h].o[i-siz]=c[x].o[i];
		c[h].o[i]=0;
		c[h].cnt++;
		c[x].s[c[x].o[i]]--;
		c[x].v[bev(c[x].o[i])]--;
		c[x].o[i]=0; 
	}
	c[x].cnt-=c[h].cnt;
	c[h].nxt=c[x].nxt;
	c[x].nxt=h;
}
void modify(int x,int j,int dx){
	while(~j){
		c[j].s[x]+=dx;
		c[j].v[bev(x)]+=dx;
		j=c[j].nxt;
	}
}
void add(int x,int pos){
	ret p=getpos(pos);
	int B=p.b;
	int j=c[B].cnt;
	c[B].o[j+1]=x;
	while(j>=p.p){
		swap(c[B].o[j],c[B].o[j+1]);
		j--;
	}
	modify(x,p.b,1);
	c[B].cnt++;
	if(c[B].cnt>=450)split(B);
}
void change(int pos,int y){
	ret p=getpos(pos);
	modify(c[p.b].o[p.p],p.b,-1);
	       c[p.b].o[p.p]=y;
	modify(c[p.b].o[p.p],p.b,+1);
}
int sum=0; 
int main(){
	//freopen("1.in","r",stdin);
	//freopen("1.my","w",stdout); 
	int n=in();
	for(int i=1;i<=n;i++){
		int v=in()+1;
		int bv=(v-1)/lv+1;
		c[h].s[v]++;
		c[h].v[bv]++;
		c[h].o[++c[h].cnt]=v;
		if(c[h].cnt>=ls)h++;
	}
	sum=n;
	for(int i=2;i<=h;i++){
		c[i-1].nxt=i;
		for(int j=1;j<=70000;j++){
			c[i].s[j]+=c[i-1].s[j];
		}
		for(int j=1;j<=300;j++){
			c[i].v[j]+=c[i-1].v[j];
		}
	}
	c[h].nxt=-1;
	int ls=0;
	int m=in();
	for(int i=1;i<=m;i++){
		char op=getaph();
		if(op=='Q'){
			int l=in()^ls,r=in()^ls,k=in()^ls;
			//printf("%d %d %d\n",l,r,k);
			ls=(query(l,r,k)-1);
//			if(ls==-2){
//				puts("RE:ls=-2");
//				printf("l=%d r=%d k=%d",l,r,k);
//				return 1;
//			}
			printf("%d\n",ls);
//			ls=0;
		}
		if(op=='M'){
			int p=in()^ls,v=(in()^ls);
			//printf("%d %d\n",p,v);
			change(p,v+1);
		}
		if(op=='I'){
			sum++;
			int p=in()^ls,v=(in()^ls);
			//printf("%d %d\n",p,v);
			add(v+1,p);
		}
		if(op=='W'){
			int j=1;
			while(~j){
				for(int i=1;i<=c[j].cnt;i++){
					printf("%d ",c[j].o[i]-1);
				}
				j=c[j].nxt;
			}
			puts("");
		}
	}
	return 0;
}