预处理块到$l[i]\sim n$答案,
对询问时,由于已经处理好了区间 $[l[p+1],R]$ 的答案,现在暴力处理不足一段的区间。
就是
$L\sim r[p]$ 在 $[L,R]$ 对答案的贡献,
也就是
$\forall i\in[L,r[p]],j\in[L,R], a[i]~ xor~ a[i+1]~ xor~ \cdots~ xor~ a[j]$ 的最大值。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
using namespace std;
const int N=12e4+5;
const int B=112;
inline void qr(int &x)
{
char c=gc;int f=1;x=0;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(int x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
struct node{int son[2],s;}t[N*31];int cnt,root[N];
void update(int y,int x,int d)
{
root[x]=++cnt;
int now=cnt,last=root[y];
t[now]=t[last];
for(int i=30;~i;i--)
{
int c=d>>i&1;
t[now].son[c]=++cnt;
now=t[now].son[c];last=t[last].son[c];
t[now]=t[last];++t[now].s;
}
}
int query(int y,int x,int d)
{
int now=root[x],last=root[y],ans=0;
for(int i=30;~i;i--)
{
int c=d>>i&1;
if(t[now].son[c^1]-t[last].son[c^1])
ans|=1<<i,now=t[now].son[c^1],last=t[last].son[c^1];
else now=t[now].son[c],last=t[last].son[c];
}
return ans;
}
int f[B][N],pos[N],l[B],r[B],a[N];
int main()
{
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
int n,m;qr(n),qr(m);
update(0,0,0);
for(int i=1;i<=n;i++)qr(a[i]),a[i]^=a[i-1],update(i-1,i,a[i]);
int bl=sqrt(n),sz=bl;
for(int i=1;i<=sz;i++)
{
l[i]=r[i-1]+1;r[i]=i*bl;
for(int j=l[i];j<=r[i];j++)pos[j]=i;
}
if(r[sz]<n){l[sz+1]=r[sz]+1;r[++sz]=n;for(int i=l[sz];i<=r[sz];i++)pos[i]=sz;}
for(int i=1;i<=sz;i++)
for(int j=l[i]+1;j<=n;j++)
f[i][j]=max(f[i][j-1],query(l[i]-1,j-1,a[j]));//A[l[i]]~A[j]的xor的最大值
int ans=0;
while(m--)
{
int L,R;qr(L),qr(R);
L=(1ll*L+ans)%n+1;R=(1ll*R+ans)%n+1;
if(L>R)swap(L,R);
L--;
int p=pos[L],q=pos[R];
ans=0;
if(p==q)
{
for(int i=L;i<=R;i++)
ans=max(ans,query(L,R,a[i]));//s[j]xors[i]means(a[i] xor a[i+1] xor...xor a[j])
}
else
{
ans=f[p+1][R];
for(int i=L;i<=r[p];i++)
ans=max(ans,query(L,R,a[i]));
}
qw(ans);puts("");
}
return 0;
}
最后一次更新于2019-10-15
0 条评论