题目
Description
taorunz平时最喜欢的东西就是可移动存储器了……只要看到别人的可移动存储器，他总是用尽一切办法把它里面的东西弄到手。
突然有一天，taorunz来到了一个密室，里面放着一排可移动存储器，存储器里有非常珍贵的OI资料……不过比较特殊的是，每个存储器上都写着一个非负整数。taorunz很高兴，要把所有的存储器都拿走（taorunz的智商高达500，他一旦弄走了这里的所有存储器，在不久到来的AHOI和NOI中……你懂的）。不过这时有一个声音传来：“你只能拿走这里的一个存储器，而且还不能直接拿，你需要指定一段区间[l, r]，满足l<r，然后在第l个和第r个存储器之间选一个拿走，你能获得的知识增加量等于区间[l, r]中所有存储器上写的整数的次大值与你拿走的这个存储器上写的整数作按位异或运算的结果。”
问题是，这里的可移动存储器数量太多，而且，它们还在不断地发生变化，有时候天上会掉下来一个新的存储器，并插入到这一排存储器中，有时候某个存储器会不明原因消失，有时候某个存储器上写的整数变化了。taorunz虽然智商很高，但也无法应对如此快的变化，他指定了许多段区间，让你帮他找出如果在这个区间中拿走存储器，他能获得的最多的知识是多少。
Input
第一行两个整数N、M，表示一开始的存储器数和后面发生的事件数。
第二行N个非负整数，表示一开始从左到右每个存储器上写的数字。注意，存储器从0开始编号，也就是最左边的存储器是第0个。
接下来M行，每行描述一个事件，有4种可能的事件。
（1）I x y：表示天上掉下来一个写着数字y的存储器，并插入到原来的第x个存储器之前，如果x等于原来存储器的个数，则插入到末尾；
（2）D x：表示第x个存储器消失；
（3）C x y：表示第x个存储器上写的数字变为y；
（4）F l r：表示taorunz指定区间[l, r]，让你告诉他最多能获得多少知识。
注意，本题强制在线，也就是事件中出现的所有数字都进行了加密，数字s表示的真实值是
对于I、D、C事件中的x及F事件中的l、r：(s+last_ans) mod n0；
对于I、C事件中的y：(s+last_ans) mod 1048576。
其中n0为目前存储器个数，last_ans为上一个F事件的结果，如果前面尚未发生F事件，则last_ans=0。
Output
对于每个F事件，输出结果。
Sample Input
5 10
2 6 3 8 7
F 1 4
I 2 1048565
I 0 1048566
D 3
F 3 0
I 3 1048569
D 5
C 1 1048570
F 1 2
F 2 1
Sample Output
15
7
4
7
HINT
1<=N, M<=100000。所有F事件满足l<r。
本题共有5组数据，除1组为随机数据外，其它数据均为人工构造。
题解
单点插入+单点删除+单点修改+区间次大值+区间求$x$的异或最大值？
分块套$Trie$！
算了算时间复杂度要跑$13s$多……
但是$rank1$的大爷说分块控制块大小的话能跑很快
注意：
如果x等于原来存储器的个数，则插入到末尾
我在写的时候看到这句话以为是出题人要选手特判情况……于是一直WA
原来ta要表达的是存储器的编号从$0$开始编号……
块的大小初始定为$k=5.7\times \sqrt n$，如果一个块大小大于$5k$或小于$\frac{k}{5}$就重构所有块
跑的还是很快的，暂居$rank3$
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<vector>
# include<cmath>
# include<algorithm>
# define X first
# define Y second
# define mp make_pair
# define Pi pair<int,int>
using namespace std;
const int MAX=2e5+5,N=2600,M=2e6+5,mod=1048576;
int n,m,k,tot,Top,_N,Sum;
int a[MAX],st[MAX],rt[N],mx[N],_mx[N],pos[MAX],bl[N],br[N];
struct Trie{
int siz[M];
int son[M][2];
int GET_POINT() {return Top?st[Top--]:(++tot);}
void ins(int &k,int x,int o=31)
{
if(!k) k=GET_POINT(),siz[k]=0;
++siz[k];
if(o==-1) return;
if(x&(1<<o)) ins(son[k][1],x,o-1);
else ins(son[k][0],x,o-1);
}
void del(int &k,int x,int o=31)
{
if(!--siz[k]) st[++Top]=k;
if(o==-1) return void(!siz[k]?k=0:0);
if(x&(1<<o)) del(son[k][1],x,o-1);
else del(son[k][0],x,o-1);
if(!siz[k]) k=0;
}
void GET_MAX(int k,int id,int &x,int o=31)
{
if(o==-1) return void(siz[k]>1?_mx[id]=x:0);
if(siz[son[k][1]]) x+=(1<<o),GET_MAX(son[k][1],id,x,o-1);
else GET_MAX(son[k][0],id,x,o-1);
}
void GET_MAX(int id)
{
mx[id]=0,_mx[id]=-1,GET_MAX(rt[id],id,mx[id]);
if(_mx[id]!=-1) return;
del(rt[id],mx[id]),_mx[id]=0,GET_MAX(rt[id],id,_mx[id]),ins(rt[id],mx[id]);
}
int ask(int k,int x,int o=31)
{
if(o==-1) return 0;
int v=bool(x&(1<<o))^1;
if(siz[son[k][v]]) return ask(son[k][v],x,o-1)+(1<<o);
return ask(son[k][v^1],x,o-1);
}
}Tree;
vector<int> vec[N];
char A[5];
void RE_BUILD()
{
int _M=0;
memset(Tree.son,0,sizeof(Tree.son));
memset(bl,0,sizeof(bl));
for(int i=1;i<=_N;vec[i++].clear())
for(int j=0,cnt=vec[i].size();j<cnt;++j)
a[++_M]=vec[i][j];
k=5.7*sqrt(_M),_N=(_M-1)/k+1,tot=Top=0;
for(int i=1,x;i<=_M;++i)
{
pos[i]=x=(i-1)/k+1,br[x]=i;
if(!bl[x]) bl[x]=i,rt[x]=0;
Tree.ins(rt[x],a[i]),vec[x].push_back(a[i]);
}
for(int i=1;i<=_N;++i)
Tree.GET_MAX(i);
}
void Ins(int x,int val)
{
int id,sum=0;
for(id=1;id<=_N;++id)
{
sum+=vec[id].size();
if(sum>=x) {sum-=vec[id].size();break;}
}
vec[id].insert(vec[id].begin()+x-sum-1,val),++Sum,Tree.ins(rt[id],val);
if(val>mx[id]) _mx[id]=mx[id],mx[id]=val;
else if(val==mx[id]) _mx[id]=val;
else if(val>_mx[id]) _mx[id]=val;
if(vec[id].size()>k*5) RE_BUILD();
}
void Del(int x)
{
int id,sum=0;
for(id=1;id<=_N;++id)
{
sum+=vec[id].size();
if(sum>=x) {sum-=vec[id].size();break;}
}
Tree.del(rt[id],vec[id][x-sum-1]),vec[id].erase(vec[id].begin()+x-sum-1),--Sum,Tree.GET_MAX(id);
if(vec[id].size()<k/5) RE_BUILD();
}
void Upt(int x,int val)
{
int id,sum=0;
for(id=1;id<=_N;++id)
{
sum+=vec[id].size();
if(sum>=x) {sum-=vec[id].size();break;}
}
Tree.del(rt[id],vec[id][x-sum-1]),vec[id][x-sum-1]=val,Tree.ins(rt[id],val),Tree.GET_MAX(id);
}
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
pair<Pi,Pi> GET_BLOCK(int l,int r)
{
int sum=0,sum1,L=0,R;
for(int i=1,cnt;i<=_N;++i)
{
sum+=(cnt=vec[i].size());
if(sum>=l&&!L) L=i,sum1=sum-cnt;
if(sum>=r) {R=i;break;}
}
return mp(mp(L,sum1),mp(R,sum-vec[R].size()));
}
int ask(int l,int r,int id)
{
if(l>r) swap(l,r);
pair<Pi,Pi> A=GET_BLOCK(l,r);
int ans=0,_ans=0,xans=0,Pl=A.X.X,Pr=A.Y.X;
if(Pl==Pr)
{
if(l==A.X.Y+1&&r==A.X.Y+vec[Pl].size()) return Tree.ask(rt[Pl],_mx[Pl]);
for(int i=l-A.X.Y-1;i<r-A.X.Y;++i)
if(vec[Pl][i]>ans) _ans=ans,ans=vec[Pl][i];
else if(vec[Pl][i]==ans) _ans=ans;
else if(vec[Pl][i]>_ans) _ans=vec[Pl][i];
for(int i=l-A.X.Y-1;i<r-A.X.Y;++i)
xans=max(xans,_ans^vec[Pl][i]);
return xans;
}
int L=Pl+(l!=A.X.Y+1),R=Pr-(r!=A.X.Y+vec[Pl].size());
for(int i=L;i<=R;++i)
{
if(mx[i]>ans) _ans=ans,ans=mx[i];
else if(mx[i]==ans) _ans=ans;
else if(mx[i]>_ans) _ans=mx[i];
if(_mx[i]>_ans) _ans=_mx[i];
}
if(L!=Pl) for(int i=vec[Pl].size()-1;i>=l-A.X.Y-1;--i)
if(vec[Pl][i]>ans) _ans=ans,ans=vec[Pl][i];
else if(vec[Pl][i]==ans) _ans=ans;
else if(vec[Pl][i]>_ans) _ans=vec[Pl][i];
if(R!=Pr) for(int i=0;i<r-A.Y.Y;++i)
if(vec[Pr][i]>ans) _ans=ans,ans=vec[Pr][i];
else if(vec[Pr][i]==ans) _ans=ans;
else if(vec[Pr][i]>_ans) _ans=vec[Pr][i];
for(int i=L;i<=R;++i)
xans=max(xans,Tree.ask(rt[i],_ans));
if(L!=Pl) for(int i=vec[Pl].size()-1;i>=l-A.X.Y-1;--i)
xans=max(xans,vec[Pl][i]^_ans);
if(R!=Pr) for(int i=0;i<r-A.Y.Y;++i)
xans=max(xans,vec[Pr][i]^_ans);
return xans;
}
int main()
{
Sum=n=read(),m=read(),k=5.7*sqrt(n),_N=(n-1)/k+1;
for(int i=1,x;i<=n;++i)
a[i]=read(),pos[i]=x=(i-1)/k+1,Tree.ins(rt[x],a[i]),vec[x].push_back(a[i]);
for(int i=1;i<=_N;++i)
Tree.GET_MAX(i);
int _cnt=0;
for(int i=1,ans=0,x;i<=m;++i)
{
scanf("%s",A),x=(read()+ans)%Sum+1;
if(A[0]=='I') Ins(x,(read()+ans)%mod);
else if(A[0]=='D') Del(x);
else if(A[0]=='C') Upt(x,(read()+ans)%mod);
else if(A[0]=='F') ++_cnt,printf("%d\n",ans=ask(x,(read()+ans)%Sum+1,_cnt));
}
return 0;
}
