Problem

Luogu

Codeforces

Solution

由于异或允许结合律，所以我们对于一段数列，只需要递推得到即可。

设 f[i][j] 为 第 i 层的第 j 个数，也可以说为 这是以第 j 个数为结尾，长度为 i 的异或和。

所以我们递推出 f 然后在用 dp 求出 max 数组即可。

Code

#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

#define N 5050

int n, q, f[N][N], maxn[N][N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &f[i][0]);
        maxn[i][0] = f[i][0];
    }
    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j <= n - i; j++)
        {
            f[j][i] = f[j][i - 1] ^ f[j + 1][i - 1];
            maxn[j][i] = max(f[j][i], max(maxn[j][i - 1], maxn[j + 1][i - 1]));
        }
    }
    scanf("%d", &q);
    for (int i = 1, l, r; i <= q; i++)
    {
        scanf("%d%d", &l, &r);
        printf("%d\n", maxn[l][r - l]);
    }
    return 0;
}