Codeforces 620F Xors on Segments（暴力+DP）
题目链接 Xors on Segments
预处理出$x[i]$ $=$ $1$ $xor$ $2$ $xor$ $3$ $xor$ $……$ $xor$ $i$
话说这题$O(n^{2})$居然能过
先对询问离线。
然后$dp[i]$表示以$a[i]$为开头的所有连续序列中最大答案。
然后依次处理到$a[j]$的时候如果以$j$为右端点的询问的左端点小于等于$i$则更新。
复杂度$O(n^{2})$
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
int x[1000010], a[50010], l[50010], r[50010], ans[5010];
vector < pair <int, int> > v[50010];
int n, q;
int main(){
rep(i, 1, 1000001) x[i] = x[i - 1] ^ i;
scanf("%d%d", &n, &q);
rep(i, 1, n) scanf("%d", a + i);
rep(i, 1, q){
scanf("%d%d", l + i, r + i);
v[r[i]].push_back({l[i], i});
}
rep(i, 1, n){
int dp = 0;
rep(j, i, n){
dp = max(dp, x[a[i]] ^ x[a[j]] ^ min(a[i], a[j]));
for (auto u : v[j]){
if (u.first <= i) ans[u.second] = max(ans[u.second], dp);
}
}
}
rep(i, 1, q) printf("%d
", ans[i]);
return 0;
}