前置知识
解法
考虑分块预处理整块的答案，散块直接暴力。
设 \(f_{i,j}\) 表示以 \(i\) 所在的块的左端点为左端点，\(j\) 为右端点的最大异或和，可持久化 01-Trie 维护即可。
- 本题中这种写法比处理整块到整块的答案更容易处理些。
整块的答案直接继承，枚举散块内的点判断即可。
理论块长取 \(\frac{n\sqrt{m \log_{2}{V}}}{m}\)，但实测取 \(176\) 最快。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
struct PDS_Trie
{
int root[12010],rt_sum=0;
struct Trie
{
int cnt,ch[2];
}tree[12010*40];
int build()
{
rt_sum++;
return rt_sum;
}
void insert(int pre,int &rt,int s)
{
rt=build();
int p=rt,q=pre;
tree[p].cnt=tree[q].cnt+1;
for(int i=31;i>=0;i--)
{
for(int j=0;j<=1;j++)
{
tree[p].ch[j]=tree[q].ch[j];
}
tree[p].ch[(s>>i)&1]=build();
p=tree[p].ch[(s>>i)&1];
q=tree[q].ch[(s>>i)&1];
tree[p].cnt=tree[q].cnt+1;
}
}
int query(int rt1,int rt2,int s)
{
int ans=0;
for(int i=31;i>=0;i--)
{
if(tree[rt2].ch[((s>>i)&1)^1]-tree[rt1].ch[((s>>i)&1)^1]>=1)
{
ans|=(1<<i);
rt1=tree[rt1].ch[((s>>i)&1)^1];
rt2=tree[rt2].ch[((s>>i)&1)^1];
}
else
{
rt1=tree[rt1].ch[(s>>i)&1];
rt2=tree[rt2].ch[(s>>i)&1];
}
}
return ans;
}
int ask(int l,int r,int s)
{
l++;
r++;
return query(root[l-1],root[r],s);
}
}T;
int L[12010],R[12010],pos[12010],a[12010],sum[12010],f[900][12010],klen,ksum;
void init(int n,int m)
{
klen=n*sqrt(m*32)/m+1;
ksum=n/klen;
for(int i=1;i<=ksum;i++)
{
L[i]=R[i-1]+1;
R[i]=R[i-1]+klen;
}
if(R[ksum]<n)
{
ksum++;
L[ksum]=R[ksum-1]+1;
R[ksum]=n;
}
for(int i=1;i<=ksum;i++)
{
for(int j=L[i];j<=R[i];j++)
{
pos[j]=i;
}
for(int j=L[i];j<=n;j++)
{
f[i][j]=max(f[i][j-1],T.ask(L[i],j,sum[j]));
}
}
}
int query(int l,int r)
{
int ans=0;
if(pos[l]==pos[r])
{
for(int i=l;i<=r;i++)
{
ans=max(ans,T.ask(l,r,sum[i]));
}
}
else
{
ans=f[pos[l]+1][r];
for(int i=l;i<=R[pos[l]];i++)
{
ans=max(ans,T.ask(l,r,sum[i]));
}
}
return ans;
}
int main()
{
int n,m,ans=0,pos=1,l,r,i;
cin>>n>>m;
T.insert(T.root[0],T.root[1],0);
for(i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]^a[i];
pos++;
T.insert(T.root[pos-1],T.root[pos],sum[i]);
}
init(n,m);
for(i=1;i<=m;i++)
{
cin>>l>>r;
l=(l%n+ans%n)%n+1;
r=(r%n+ans%n)%n+1;
if(l>r)
{
swap(l,r);
}
ans=query(l-1,r);
cout<<ans<<endl;
}
return 0;
}