Problem
给定一个长度为\(N\)的非负整数数列
有个\(M\)询问,询问格式为\(L,R\),表示询问区间\([L,R]\)内的最大的连续异或和。
即求出\(max( A_i \ xor \ A_{i+1} \ xor \ A_{i+2} \ xor \ ... \ xor \ A_j )\) 其中\((L \leq i \leq j \leq R)\)
强制在线
\(1 \leq N \leq 12000,1 \leq M \leq 6000,1 \leq A_i \leq 2^{31}-1\)
Solution
分析题目性质,因为异或\((xor)\)操作有自反性,所以可以用前缀异或和来维护一段连续异或和,即\([l,r]\)异或和\(=sum[r]\ xor \ sum[l-1]\)
那么此题就被转换成了求区间\([L,R]\)的最大的\(sum[j]\ xor\ sum[i-1] \ (L \leq i \leq j \leq R)\)
显然这个问题可以用\(dp\)来做
\(f[i][j]:\)区间\([i,j]\)内任意两数异或之和最大
\(f[i][j]=max(f[i][j-1],sum[l]\)^\(sum[j])\ (i \leq l < j)\)
时间复杂度\(O(n^3)\),爆炸,考虑优化
发现\(sum[l]\)^\(sum[j]\)相当于是从\([i,j)\)中找一个数异或上\(sum[j]\)最大,考虑可持久化\(01trie\)计算,时间复杂度被优化到了\(O(n^2logn)\),可依然要炸。
那么直接考虑可持久化\(01trie\),暴力枚举\(i\),在\(trie\)上找异或\(sum[i]\)最大的\(sum[j]\),单次询问时间复杂度\(O(nlogn)\),有\(M\)次询问,也要炸。
注意到\(1 \leq N \leq 12000\),考虑将\(N\)个前缀异或和分块,对每一块进行预处理\(f\)数组,然后询问时暴力查询不是块的部分,是完整块的直接用事先预处理好的即可。
详细的说呢,就是
\(f[i][j]:\)从第\(i\)块开头到第\(j\)块结尾这一段里任意两个数异或最大值
\(f[i][j]=max(f[i][j-1],sum[l]\)^\(sum[k])\)
\(l\)枚举\(j\)块内元素,\(k\)枚举的是\(i\)到\(j-1\)块的元素。
发现这里同样可以跟上面一样用可持久化\(01trie\)优化,于是时间复杂度变成了\(O((\sqrt n)^3logn) = O(n\sqrt nlogn)\)
对于每次询问时间复杂度\(O(2\sqrt nlogn)\)。
预处理空间复杂度\(O(n)\),\(trie\)树\(O(nlogn)\)
\(code:\)
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 15000 + 5;
const int MAX_S = 200 + 5;
typedef long long ll;
int n,m,s,tot,sum[MAX_N];
ll f[MAX_S][MAX_S],lastans,a[MAX_N];
inline int calc(int x){return (x-1)/s+1;}
int root[MAX_N];
struct PTrie{
int num;
int nxt[2];
}Ptrie[MAX_N * 32];
void Pins(ll x,int id){
root[id]=++tot;
int p=root[id],q=root[id-1];
for(int i=30;i>=0;i--){
int c=(x>>i)&1;
for(int j=0;j<2;j++)
Ptrie[p].nxt[j]=Ptrie[q].nxt[j];
Ptrie[p].num=Ptrie[q].num+1;
Ptrie[p].nxt[c]=++tot;
p=Ptrie[p].nxt[c];
q=Ptrie[q].nxt[c];
}
Ptrie[p].num=Ptrie[q].num;
Ptrie[p].num++;
}
ll Pask(ll x,int a,int b){
int q=root[a-1],p=root[b];
ll ans=0;
for(int i=30;i>=0;i--){
int c=(x>>i)&1;
int ps=Ptrie[p].nxt[c^1],qs=Ptrie[q].nxt[c^1];
if(Ptrie[ps].num-Ptrie[qs].num>=1){
ans|=(1ll<<i);
p=ps;
q=qs;
}
else{
p=Ptrie[p].nxt[c];
q=Ptrie[q].nxt[c];
}
}
return ans;
}
ll query(int l,int r){
int kl=calc(l),kr=calc(r);
ll ans=0;
if(kl==kr){
for(int i=l;i<=r;i++){
ans=max(ans,Pask(sum[i],l,i));
}
}
else{
ans=0;
if(kl+1<=kr-1) ans=f[kl+1][kr-1];
for(int i=l;i<=kl*s;i++)
ans=max(ans,Pask(sum[i],l,r));
for(int i=(kr-1)*s+1;i<=r;i++)
ans=max(ans,Pask(sum[i],l,r));
}
return ans;
}
int main(){
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
scanf("%d%d",&n,&m);
s=sqrt(n);
Pins(sum[0],0);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
sum[i]=sum[i-1]^a[i];
Pins(sum[i],i);
}
for(int i=1;i<=calc(n);i++){
for(int j=i;j<=calc(n);j++){
ll maxn=0;
for(int l=(j-1)*s+1;l<=j*s;l++)
maxn=max(maxn,Pask(sum[l],(i-1)*s+1,l));
f[i][j]=max(f[i][j-1],maxn);
}
}
while(m--){
ll x,y;
scanf("%lld%lld",&x,&y);
ll l=(x+lastans)%n+1;
ll r=(y+lastans)%n+1;
if(l>r) swap(l,r);
lastans=query(l-1,r);
printf("%lld\n",lastans);
}
return 0;
}