题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3217
分块过掉辣！！！！！！$O(n^{1.5}+q\times \sqrt{n})$的分块过掉辣！！
而且速度贼快内存贼小啊（成功踩到b站第一）
由于此题需要强制在线的删除或者插入，所以我们基于块状链表分块，在每个块内存储指定区间内的所有数，以及该区间内的最大值和次大值，同时再维护一个由该区间内所有数组成的trie树。
对于修改一个数，首先在该块的trie数中删除该数（直接伪删），然后再插入，接着更新最大值和次大值。
对于插入一个数，直接在trie树中插入该数，随后在块状链表中插入，更新最大值和次大值。最后判断是否要将该块拆分（如果要察费直接暴力重构两个块即可）
对于删除一个数，trie树伪删除+块链删除+更新最大值和次大值。随后判断该块大小是否等于0（为零可以直接删掉这个块了）
对于查询最大值，首先查询出该区间内的次大值。对于完全包含的块，直接将该值丢到该块的trie树中求最大值，对于非完全包含的块，直接暴力求即可。
PS：经过测试，每个块的大小设置为3200最好（达到3200后切成两块1600的）。最初块大小为400，b站上跑了15.5s，把块大小改为3200后变成3.8s，直接rank1了。
UPD：前段时间被卡到第二，后来重新把块大小调整为2620，并且加上fread与fwrite，卡到3312ms，重回rank1。
（不知能否继续优化.....）
#include<bits/stdc++.h>
#define M 5000000
#define N 100
using namespace std;
struct trie{
int a[],sum;
}p[M]; int uset=;
int add(int now,int x,int px){
if(!now) now=++uset;
int ret=now;
for(int i=;i>=;i--){
bool k=x&(<<i); p[now].sum+=px;
if(p[now].a[k]) now=p[now].a[k];
else uset++,p[now].a[k]=uset,now=uset;
}
p[now].sum+=px;
return ret;
}
int getmax(int now,int x){
int ans=;
for(int i=;i>=;i--){
bool k=x&(<<i);
if(p[p[now].a[-k]].sum)
now=p[now].a[-k],ans+=(<<i);
else now=p[now].a[k];
}
return ans;
}
struct kuai{
int rt,use,next;
int max1,max2,a[N*+];
kuai(){
rt=use=next=max1=max2=;
memset(a,,sizeof(a));
}
void getmax(){
max1=max2=;
for(int i=;i<=use;i++)
if(a[i]>max1) max2=max1,max1=a[i];
else if(a[i]>max2) max2=a[i];
}
}a[N*]; int use=;
void updata(int id,int zhi){
for(int i=;i;i=a[i].next)
if(a[i].use>=id){
int last=a[i].a[id]; a[i].a[id]=zhi;
a[i].rt=add(a[i].rt,last,-);
add(a[i].rt,zhi,);
a[i].getmax();
return;
}else id-=a[i].use;
}
void cut(int i){
int j=++use;
a[i].use=a[j].use=N*;
a[j].next=a[i].next; a[i].next=j;
for(int k=;k<=N*;k++)
a[j].a[k]=a[i].a[k+N*],a[i].a[k+N*]=;
a[i].max1=a[i].max2=;
a[i].getmax(); a[j].getmax();
a[i].rt=add(,a[i].a[],);
a[j].rt=add(,a[j].a[],);
for(int k=;k<=N*;k++){
add(a[i].rt,a[i].a[k],);
add(a[j].rt,a[j].a[k],);
}
}
void insert(int x,int id){
int i,pre;
for(i=;i;pre=i,i=a[i].next)
if(a[i].use<id) id-=a[i].use;
else break;
if(!i) i=pre,id+=a[i].use;
for(int j=a[i].use;j>=id;j--) a[i].a[j+]=a[i].a[j];
a[i].a[id]=x; a[i].use++;
a[i].rt=add(a[i].rt,x,);
if(x>a[i].max1) a[i].max2=a[i].max1,a[i].max1=x;
else if(x>a[i].max2) a[i].max2=x;
if(a[i].use>=N*) cut(i);
}
void del(int id){
int i,pre=,x;
for(i=;i;pre=i,i=a[i].next)
if(a[i].use<id) id-=a[i].use;
else break;
x=a[i].a[id]; add(a[i].rt,x,-);
for(int j=id;j<=a[i].use;j++) a[i].a[j]=a[i].a[j+];
a[i].use--;
if(a[i].use==) {a[pre].next=a[i].next; return;}
if(a[i].max2>x) return;
a[i].getmax();
}
int getmax2(int l,int r){
int max1=,max2=,sum=;
int i,pre;
for(i=;i;pre=i,i=a[i].next){
if(l<=sum+&&sum+a[i].use<=r){
if(a[i].max1>max1) max2=max1,max1=a[i].max1;
else if(a[i].max1>max2) max2=a[i].max1;
if(a[i].max2>max2) max2=a[i].max2;
}
else if(sum+<=l&&r<=sum+a[i].use){
for(int j=l-sum;j<=r-sum;j++)
if(a[i].a[j]>max1) max2=max1,max1=a[i].a[j];
else if(a[i].a[j]>max2) max2=a[i].a[j];
}
else if(sum+<=l&&l<=sum+a[i].use){
for(int j=l-sum;j<=a[i].use;j++)
if(a[i].a[j]>max1) max2=max1,max1=a[i].a[j];
else if(a[i].a[j]>max2) max2=a[i].a[j];
}
else if(sum+<=r&&r<=sum+a[i].use){
for(int j=;j<=r-sum;j++)
if(a[i].a[j]>max1) max2=max1,max1=a[i].a[j];
else if(a[i].a[j]>max2) max2=a[i].a[j];
}
sum+=a[i].use;
}
return max2;
}
int query(int l,int r){
int x=getmax2(l,r),maxn=,sum=;
int i,pre;
for(i=;i;pre=i,i=a[i].next){
if(l<=sum+&&sum+a[i].use<=r){
maxn=max(maxn,getmax(a[i].rt,x));
}
else if(sum+<=l&&r<=sum+a[i].use){
for(int j=l-sum;j<=r-sum;j++)
maxn=max(maxn,x^a[i].a[j]);
}
else if(sum+<=l&&l<=sum+a[i].use){
for(int j=l-sum;j<=a[i].use;j++)
maxn=max(maxn,x^a[i].a[j]);
}
else if(sum+<=r&&r<=sum+a[i].use){
for(int j=;j<=r-sum;j++)
maxn=max(maxn,x^a[i].a[j]);
}
sum+=a[i].use;
}
return maxn;
}
int main(){
int n,m,lastans=,n0;
scanf("%d%d",&n,&m); n0=n;
for(int i=;i<=n;i++){
int x; scanf("%d",&x);
insert(x,i);
}
while(m--){
char c[]; int x,y;
scanf("%s%d",c,&x);
x=(x+lastans)%n0+;
if(c[]=='D'){del(x); n0--;continue;}
scanf("%d",&y);
if(c[]=='F') y=(y+lastans)%n0+;
else y=(y+lastans)%;
if(c[]=='I') insert(y,x),n0++;
if(c[]=='C') updata(x,y);
if(c[]=='F') printf("%d\n",lastans=query(min(x,y),max(x,y)));
}
}