题意：带插入、修改的区间k小值在线查询。
考虑分块，但是用链表将块连起来。
用未来日记的 ，将值域和下标分块，有以下定义：
- 表示前 块中，值域在 中的个数有多少
- 表示前 块中 的个数
- 表示在散块中值域为 的个数
- 表示在散块中值为 的个数。
由于使用了链表，所以上面的东西用一个 封装起来。
插入和修改的操作都是在 个块中扫一遍即可。
但是若在同一个位置插入很多次，在查询的时候，复杂度会爆炸（查询在散块中）。于是考虑能不能将某个块长超标的块分裂成两个块。
显然是可行的。设一个上界 ，当快长大于 时，将其分成两块即可。
复杂度是 。常数有点大。
#include<bits/stdc++.h>
#define bg(x) (siz*(x-1)+1)
#define ed(x) (siz*x)
using namespace std;
const int N=2e5+50,M=600;
int valcnt[M][N],cnt[M][M],belong[N];
class block
{
public:
int la[M*2+50],val[M*2+50],siz,fir=1,id;
inline void insert(int x)
{
la[siz]=1+siz;++siz;val[siz]=x;
cnt[id][belong[x]]++;
valcnt[id][x]++;
}
inline void insert(int x,int v)
{
++siz;val[siz]=v;
int p=fir,pre=0;
while(--x)pre=p,p=la[p];
la[siz]=p;if(p==fir)fir=siz;else la[pre]=siz;
}
}b[M<<1];
int tot,totnum,re[M*2],siz=600,n,las,q,a[N],P[M],p[N],la[M*2],mx;
char ch,B0[1<<15],*S=B0,*T=B0;
#define getc() (S==T&&(T=(S=B0)+fread(B0,1,1<<15,stdin),S==T)?0:*S++)
int aa;inline int read(){
while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
inline void split(int t)
{
++tot;b[tot].id=tot;
la[tot]=la[t];
la[t]=tot;
int num=0;
for(int i=b[t].fir;i;i=b[t].la[i])re[++num]=b[t].val[i];
for(int i=1;i<=mx;i++)valcnt[tot][i]=valcnt[t][i];
for(int i=1;i<=belong[mx];i++)cnt[tot][i]=cnt[t][i];
b[t].siz=0;b[t].fir=1;
memset(b[t].la,0,sizeof b[t].la);
memset(b[t].val,0,sizeof b[t].val);
for(int i=1;i<=siz;i++)b[t].insert(re[i]),
valcnt[t][re[i]]--,cnt[t][belong[re[i]]]--;
for(int i=siz+1;i<=num;i++)b[tot].insert(re[i]),
valcnt[t][re[i]]--,cnt[t][belong[re[i]]]--,
valcnt[tot][re[i]]--,cnt[tot][belong[re[i]]]--;
}
inline int find(int x,int y,int k)
{
int l=1,r,tot=0,rk1,rk2,pre=1;
while(tot+b[l].siz<x)tot+=b[l].siz,pre=l,l=la[l];r=l;rk1=x-tot;
while(tot+b[r].siz<y)tot+=b[r].siz,pre=r,r=la[r];rk2=y-tot;
if(l==r)
{
int num=0;
for(int i=b[l].fir,vi=1;i;i=b[l].la[i],vi++)
{
if(vi>=rk1)re[++num]=b[l].val[i];
if(vi==rk2)break;
}
sort(re+1,re+1+num);return re[k];
}
for(int i=1;i<=belong[mx];i++)P[i]=0;
for(int i=b[l].fir,vi=1;i;i=b[l].la[i],vi++)if(vi>=rk1)P[belong[b[l].val[i]]]++;
for(int i=b[r].fir,vi=1;i,vi<=rk2;i=b[r].la[i],vi++)P[belong[b[r].val[i]]]++;
int re=0,u=0;
while(++u)
{
if(re+P[u]+cnt[pre][u]-cnt[l][u]>=k)break;
re+=P[u]+cnt[pre][u]-cnt[l][u];
}
for(int i=bg(u);i<=ed(u);i++)p[i]=0;
for(int i=b[l].fir,vi=1;i;i=b[l].la[i],vi++)if(vi>=rk1)p[b[l].val[i]]++;
for(int i=b[r].fir,vi=1;i,vi<=rk2;i=b[r].la[i],vi++)p[b[r].val[i]]++;
for(int i=bg(u);i<=ed(u);i++)
{
re+=p[i]+valcnt[pre][i]-valcnt[l][i];
if(re>=k)return i;
}
}
inline void change(int x,int val)
{
int rk,tot=0,t=1,last_val;
while(b[t].siz+tot<x)tot+=b[t].siz,t=la[t];rk=x-tot;
for(int i=b[t].fir,vi=1;i;i=b[t].la[i],vi++)if(vi==rk)
{
last_val=b[t].val[i];
b[t].val[i]=val;
break;
}
while(t)cnt[t][belong[last_val]]--,cnt[t][belong[val]]++,
valcnt[t][last_val]--,valcnt[t][val]++,t=la[t];
}
inline void insert(int x,int val)
{
if(x==totnum)
{
int t=1,LA;
while(la[t])t=la[t];
LA=b[t].fir;
while(b[t].la[LA])LA=b[t].la[LA];
b[t].la[LA]=++b[t].siz;b[t].val[b[t].siz]=val;
cnt[t][belong[val]]++;
valcnt[t][val]++;
if(b[t].siz>=2*M)split(t);
return;
}
int rk,tot=0,t=1,pre=0,pos;
while(b[t].siz+tot<x)tot+=b[t].siz,t=la[t];rk=x-tot;pos=t;
b[t].insert(rk,val);
while(t)++cnt[t][belong[val]],++valcnt[t][val],t=la[t];
if(b[pos].siz>=2*M)split(pos);
}
main()
{
// freopen("4.in","r",stdin);
// freopen("out.txt","w",stdout);
n=totnum=read();mx=70001;
for(int i=1;i<=n;i++)a[i]=read()+1;
for(int i=1;i<=mx;i++)belong[i]=(i-1)/siz+1;
for(int i=1;i<=belong[n];i++)b[i].id=++tot,la[i]=i+1;la[belong[n]]=0;
for(int i=1;i<=n;i++)
{
if(!b[belong[i]].siz)
{
for(int j=1;j<=mx;j++)valcnt[belong[i]][j]=valcnt[belong[i]-1][j];
for(int j=1;j<=belong[mx];j++)cnt[belong[i]][j]=cnt[belong[i]-1][j];
}
b[belong[i]].insert(a[i]);
}
q=read();
while(q--)
{
char opt=getc();while(opt<'A'||opt>'Z')opt=getc();
int x=read()^las;
if(opt=='Q')
{
int y=read()^las,k=read()^las;
printf("%ld\n",(las=find(x,y,k)-1));
continue;
}
int val=(read()^las)+1;
if(opt=='M')change(x,val);
else ++totnum,insert(x,val);
}
}
