-
\(f_{i,j}\) 表示选第 \(i\) 朵花，在 \((i,j]\) 中选一朵花 \(k\)，\(\max a_i\oplus a_k\)。
-
预处理 \(f_{i,j}=\max(f_{i,j-1},a_i\oplus a_j)\)。
-
答案 \(\max f_{i,r},i\in[l,r)\).
-
复杂度 \(\mathcal{O}(n^2)\)。
View Code
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e3 + 5;
int n, m, a[N], f[N][N];
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1;i <= n;++i)
scanf("%d", &a[i]);
for(int i = 1;i < n;++i)
for(int j = i + 1;j <= n;++j)
f[i][j] = max(f[i][j - 1], a[i] ^ a[j]);
while(m--)
{
int l, r, ans = 0;
scanf("%d%d", &l, &r);
for(int i = l;i <= r;++i)
ans = max(ans, f[i][r]);
printf("%d\n", ans);
}
return 0;
}