自动搬运

查看原文

来自洛谷，原作者为

	ivyjiao 复活了

搬运于2025-08-24 23:00:18，当前版本为作者最后更新于2024-08-03 15:16:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

wukaichen888 /hs /bx

区间 DP 神仙题。

---

$N=12000$，$O(n^2)$ 可过。

考虑区间 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$，剩余的同理。

代码：

#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];
    }
}