链接：https://ac.nowcoder.com/acm/contest/11171/B
来源：牛客网
小 Q 的院子里种了 n朵彼岸花，其中第 i 朵的彼岸花的美丽值为 ai，彼岸花按照编号从小到大从左向右排成了一排。
现在小 Q 有 m 个问题，他每次会给出一个区间 [l,r][l,r]，他想在编号属于区间 [l,r][l,r] 的彼岸花中选出两朵花，使得 ai⨁aj(⨁ 表示按位异或操作) 的值最大（如果只能选出一朵花请直接输出 0）。
由于他太菜了，只能来问你了。
输入描述:
第一行两个整数 n,m(1≤n,m≤5×103)。
第二行 n 个整数，分别表示 a1,a2,...,an(1≤ai≤210)。
接下来 m 行，每行两个整数分别表示一个问题所给出的区间 l,r(1≤l≤r≤n)。
输出描述:
输出 m 行，表示每个问题的答案。
示例1
输入
复制
10 10
1 2 3 4 5 6 7 8 9 10
1 2
1 3
1 5
2 6
2 8
2 10
3 7
8 10
6 9
1 7
输出
复制
3
3
7
7
15
15
7
3
15
7
最简单的还是DP，可以解决静态查找区间最值的问题。设dp[i, j]表示i到j区间任取两个数能够异或出来的最大值，初始化dp[i, j] = a[i] ^ a[j]，有转移方程:(dp[i, j] = max(dp[i, j], dp[i + 1, j], dp[i, j - 1]))。即i到j的能够异或出来的最大值可能从i到j - 1，i + 1到j以及a[i]^a[j]中取得。注意遍历的顺序。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
long long a[5005], dp[5005][5005];
#define ll long long
signed main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) {
dp[i][i] = a[i];
for(int j = 1; j <= n; j++) {
dp[i][j] = a[i] ^ a[j];
}
}
for(int i = n; i >= 1; i--) {
for(int j = i + 1; j <= n; j++) {
dp[i][j] = max(dp[i][j], max(dp[i][j - 1], dp[i + 1][j]));
}
}
for(int i = 1; i <= m; i++) {
int l, r;
cin >> l >> r;
if(l == r) cout << 0 << endl;
else {
cout << dp[l][r] << endl;
}
}
return 0;
}