题解：P10690 Fotile 模拟赛 L
ivyjiao
·
·
题解
wukaichen888 /hs /bx
区间 DP 神仙题。
考虑区间 DP，第一维枚举长度，第二维枚举区间起点，然后就是 DP 转移，设 $dp_{l,r}$ 为 $\max_{l\le i\le j\le r}\bigoplus_{k=i}^{j} a_k$，则这里有一个比较显然的 DP 转移式：
$$dp_{l,r}=\max\{a_l\oplus a_{l+1}\oplus\cdots\oplus a_r,dp_{l,r-1},dp_{l+1,r}\}$$
DP 数组的初始值就是 $dp_{i,0}=a_i$。
然后考虑优化这个 $O(n^3)$ 的 DP 转移过程，不难发现异或满足 $x\oplus x=0$，所以 $a_l\oplus a_{l+1}\oplus\cdots\oplus a_r=qzh_r\oplus qzh_{l-1}$，其中 $qzh$ 是前缀异或和数组。所以我们只需要预处理出前缀异或和数组即可把该转移过程优化为 $O(n^2)$。
$$dp_{l,r}=\max\{qzh_r\oplus qzh_{l-1},dp_{l,r-1},dp_{l+1,r}\}$$
然而，这题的空间不允许你开这么大的数组，所以我们考虑继续优化该 DP。
经过计算，大概空间再减少一半就能开的下了，那么怎么优化掉一半的空间？
不难发现我们的 DP 数组其实有一半都被浪费掉了（$r<l$ 的部分），这就是本题的突破口。
C++ 中，有这么一个美妙的东西，它叫 vector 动态数组。
这个 vector 的好处就是它的大小是可以动态调整的，不像普通数组一样定下了就改不了。
但是我们发现浪费的空间并非在数组的末尾，所以我们要更改 DP 式，让浪费的空间出现在数组的末尾。
设 $dp_{l,len}$ 为 $\max_{l\le i\le j\le l+len-1}\bigoplus_{k=i}^{j} a_k$，则这里有一个比较显然的 DP 转移式：
$$dp_{l,len}=\max\{qzh_{l+len-1}\oplus qzh_{l-1},dp_{l,len-1},dp_{l+1,len-1}\}$$
DP 数组的初始值就是 $dp_{i,1}=a_i$。
然后我们发现此时被浪费的空间都出现在数组的末尾了，那么如何让这些空间不被浪费？
C++ 的 vector 中，有一个函数叫做 resize，它可以控制 vector 的大小，现在这些空间就被节约下来了。
剩下的就是一些细节了，注意 $x+lastans$ 可能会爆 int，要写成 $(x\bmod n+lastans\bmod n)\bmod n$，剩余的同理。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,l,r,a[12001],qzh[12001],lastans;
vector<int>dp[12001];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
dp[i].resize(n-i+2);
dp[i][1]=a[i];
qzh[i]=qzh[i-1]^a[i];
}
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
dp[i][len]=max({qzh[i+len-1]^qzh[i-1],dp[i+1][len-1],dp[i][len-1]});
}
}
while(m--){
cin>>x>>y;
l=min(((x%n+lastans%n)%n)+1,((y%n+lastans%n)%n)+1);
r=max(((x%n+lastans%n)%n)+1,((y%n+lastans%n)%n)+1);
cout<<dp[l][r-l+1]<<'\n';
lastans=dp[l][r-l+1];
}
}
```