题目大意
给出数列 \(\text a\),询问区间 \([l,r]\) 内,满足 \(l\le i \le j\le r\) 的 \(i,j\) 使 \(a_i xor a_{i+1} xor...xor a_j\) 值最大,求这个最值
题解
这题比较新鲜,知道了一些从未知道的套路
先考虑 \(O(n^2 \log V)\) 的做法
显然对于询问 \([l,r]\) 扫一遍,用 \(Trie\) 经典地贪心求最大值即可
然后发现我们可以把扫一遍的 \(O(n)\) 级别的复杂度弄掉
就是考虑分块
求出从第 \(i\) 块第一个位置为起点到第 \(j\) 个位置的答案
可以 \(O(n\sqrt n \log V)\) 预处理出
然后查询直接查预处理的数组就可以跳过块,暴力求散的答案即可
\(Code\)
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const int N = 20005;
int n, q, t, size, a[N], sm[N], sum[64 * N], tr[32 * N][2], rt[N];
inline void update(int u , int v , int x)
{
for(register int i = 30; i >= 0; i--)
{
int c = (x >> i) & 1;
sum[v] = sum[u] + 1;
tr[v][c] = ++size;
tr[v][c ^ 1] = tr[u][c ^ 1];
v = tr[v][c] , u = tr[u][c];
}
sum[v] = sum[u] + 1;
}
inline int query(int u , int v , int x)
{
int res = 0;
for(register int i = 30; i >= 0; i--)
{
int c = (x >> i) & 1 , k = sum[tr[v][c ^ 1]] - sum[tr[u][c ^ 1]];
if (k) res += (1 << i) , u = tr[u][c ^ 1] , v = tr[v][c ^ 1];
else u = tr[u][c] , v = tr[v][c];
}
return res;
}
int st[N], ed[N], bl[N], g[155][N];
void Square()
{
int num = sqrt(n);
for(register int i = 1; i <= num; i++) st[i] = n / num * (i - 1) + 1, ed[i] = n / num * i;
ed[num] = n;
for(register int i = 1; i <= num; i++)
for(register int j = st[i]; j <= ed[i]; j++) bl[j] = i;
for(register int i = 1; i <= num; i++)
for(register int j = st[i]; j <= n; j++) g[i][j] = max(g[i][j - 1], query(rt[max(st[i] - 2, 0)], rt[j], sm[j]));
}
int main()
{
freopen("sequence.in", "r", stdin);
freopen("sequence.out", "w", stdout);
scanf("%d%d%d", &n, &q, &t);
for(register int i = 1; i <= n; i++) scanf("%d", &a[i]), sm[i] = sm[i - 1] ^ a[i];
update(0, rt[0] = ++size, 0);
for(register int i = 1; i <= n; i++) update(rt[i - 1] , rt[i] = ++size , sm[i]);
Square();
for(int l, r, ans = 0; q; --q)
{
scanf("%d%d", &l, &r);
l = (l + t * ans) % n + 1, r = (r + t * ans) % n + 1;
if (l > r) swap(l, r);
ans = 0;
int x = bl[l], y = bl[r];
if (x == y) for(register int i = l - 1; i <= r; i++) ans = max(ans, query(rt[max(l - 2, 0)], rt[r], sm[i]));
else{
ans = g[x + 1][r];
for(register int i = l - 1; i <= ed[x]; i++) ans = max(ans, query(rt[max(l - 2, 0)], rt[r], sm[i]));
for(register int i = st[y]; i <= r; i++) ans = max(ans, query(rt[max(l - 2, 0)], rt[r], sm[i]));
}
printf("%d\n", ans);
}
}