显然是块状链表的经典题。但是经典做法的复杂度是O(n*sqrt(n)*log^2(n))的，出题人明确说了会卡掉。
于是我们考虑每个块内记录前n个块的权值分块。
查询的时候差分什么的，复杂度就是O(n*sqrt(n))的了。
插入的时候为了防止块过大，要考虑裂块(细节较多)。
感谢bzoj提供O2，我的STL块链才能通过(list+vector)。
#include<cstdio>
#include<list>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
#define X first
#define Y second
int num[70001],l[270],Limit,ans,n,tmp[35001],x,y,val,m;
char op[1];
struct VAL_BLOCK
{
int b[70001],sumv[270];
void insert(const int &x){++b[x]; ++sumv[num[x]];}
void erase(const int &x){--b[x]; --sumv[num[x]];}
}S;
struct BLOCK
{
vector<int>v;
VAL_BLOCK T;
BLOCK(){}
};
list<BLOCK>List;
typedef list<BLOCK>::iterator LER;
typedef vector<int>::iterator VER;
typedef pair<LER,VER> Pair;
Pair Find(const int &p)
{
int cnt=0; LER i=List.begin();
for(;i!=List.end();++i)
{
cnt+=(*i).v.size();
if(cnt>=p)
{
cnt-=(*i).v.size();
for(VER j=(*i).v.begin();j!=(*i).v.end();++j)
if((++cnt)==p)
return make_pair(i,j);
}
}
--i; return make_pair(i,(*i).v.end());
}
void Insert(const int &p,const int &V)
{
Pair Bel=Find(p);
(*Bel.X).v.insert(Bel.Y,V);
for(LER i=Bel.X;i!=List.end();++i)
(*i).T.insert(V);
if((*Bel.X).v.size()>Limit)
{
LER Near=Bel.X; ++Near;
int Last=(*Bel.X).v.back();
if((*Near).v.size()>Limit || Near==List.end())
{
Near=List.insert(Near,BLOCK());
(*Near).T=(*Bel.X).T;
}
(*Near).v.insert((*Near).v.begin(),Last);
(*Bel.X).T.erase(Last);
(*Bel.X).v.pop_back();
}
}
void Update(const int &p,const int &V)
{
Pair Bel=Find(p);
for(LER i=Bel.X;i!=List.end();++i)
(*i).T.erase(*Bel.Y),
(*i).T.insert(V);
(*Bel.Y)=V;
}
int Kth(const int &L,const int &R,const int &K)
{
Pair P1=Find(L),P2=Find(R);
int cnt=0,res;
if(P1.X==P2.X)
{
for(VER i=P1.Y;i<=P2.Y;++i) S.insert(*i);
for(int i=1;;++i)
{
cnt+=S.sumv[i];
if(cnt>=K)
{
cnt-=S.sumv[i];
for(int j=l[i];;++j)
{
cnt+=S.b[j];
if(cnt>=K) {res=j; goto OUT2;}
}
}
} OUT2:
for(VER i=P1.Y;i<=P2.Y;++i) S.erase(*i);
return res;
}
for(VER i=P1.Y;i!=(*P1.X).v.end();++i) S.insert(*i);
for(VER i=(*P2.X).v.begin();i<=P2.Y;++i) S.insert(*i);
LER LB=P1.X,RB=P2.X; --RB;
for(int i=1;;++i)
{
cnt+=((*RB).T.sumv[i]-(*LB).T.sumv[i]+S.sumv[i]);
if(cnt>=K)
{
cnt-=((*RB).T.sumv[i]-(*LB).T.sumv[i]+S.sumv[i]);
for(int j=l[i];;++j)
{
cnt+=((*RB).T.b[j]-(*LB).T.b[j]+S.b[j]);
if(cnt>=K) {res=j; goto OUT;}
}
}
} OUT:
for(VER i=P1.Y;i!=(*P1.X).v.end();++i) S.erase(*i);
for(VER i=(*P2.X).v.begin();i<=P2.Y;++i) S.erase(*i);
return res;
}
void Val_Makeblock()
{
int tot=1,sz=sqrt(70000); if(!sz) sz=1;
for(;tot*sz<=70000;++tot)
{
l[tot]=(tot-1)*sz;
int R=tot*sz-1;
for(int i=l[tot];i<=R;++i) num[i]=tot;
}
l[tot]=(tot-1)*sz;
for(int i=l[tot];i<=70000;++i) num[i]=tot;
}
void Makeblock()
{
int sz=sqrt(n),tot=1; if(!sz) sz=1;
Limit=sqrt(n+35000);
for(;tot*sz<n;++tot)
{
LER End=List.insert(List.end(),BLOCK());
(*End).v.assign(tmp+(tot-1)*sz+1,tmp+tot*sz+1);
}
LER End=List.insert(List.end(),BLOCK());
(*End).v.assign(tmp+(tot-1)*sz+1,tmp+n+1);
}
void Init_Ts()
{
LER i=List.begin();
for(VER j=(*i).v.begin();j!=(*i).v.end();++j)
(*i).T.insert(*j);
++i;
for(LER Front=List.begin();i!=List.end();++i,++Front)
{
(*i).T=(*Front).T;
for(VER j=(*i).v.begin();j!=(*i).v.end();++j)
(*i).T.insert(*j);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&tmp[i]);
Makeblock();
Val_Makeblock();
Init_Ts();
scanf("%d",&m);
for(;m;--m)
{
scanf("%s%d",op,&x); x^=ans;
if(op[0]=='Q')
{
scanf("%d%d",&y,&val); y^=ans; val^=ans;
printf("%d\n",ans=Kth(x,y,val));
}
else if(op[0]=='M')
{
scanf("%d",&val); val^=ans;
Update(x,val);
}
else
{
scanf("%d",&val); val^=ans;
Insert(x,val);
}
}
return 0;
}