题目描述
FOTILE得到了一个长为N的序列A，为了拯救地球，他希望知道某些区间内的最大的连续XOR和。即对于一个询问，你需要求出max(Ai xor Ai+1 xor Ai+2 … xor Aj)，其中l<=i<=j<=r。为了体现在线操作，对于一个询问(x,y)：l = min ( ((x+lastans) mod N)+1 , ((y+lastans) mod N)+1 ).
r = max ( ((x+lastans) mod N)+1 , ((y+lastans) mod N)+1 ).其中lastans是上次询问的答案，一开始为0。
输入
第一行两个整数N和M。第二行有N个正整数，其中第i个数为Ai，有多余空格。后M行每行两个数x,y表示一对询问。
输出
共M行，第i行一个正整数表示第i个询问的结果。
样例输入
3 3
1 4 3
0 1
0 1
4 3
样例输出
5
7
7
题解
可持久化Trie树+分块
把区间异或和转化为前缀相异或的形式，问题就转化为：在 $[l-1,r]$ 中选出 $i$ 和 $j$ ，使得 $sum_i\text{^}sum_j$ 最大。
如果确定一个端点，另一个端点在某区间内的话，可以使用可持久化Trie树来解决。
本题两个端点都是只有区间范围限制。考虑分块，预处理出 $f[x][y]$ 表示从第 $x$ 块到第 $y$ 块的答案（这里我傻逼了，可以处理出块到端点的答案）。然后对于询问，整块直接取出答案，零碎的部分再使用可持久化Trie树暴力即可。
时间复杂度 $O(n\sqrt n\log n)$
注意本题有一个坑点：输入的x和y加上lastans后可能会爆int，因此需要预先取模再相加。
#include <cmath>
#include <cstdio>
#include <algorithm>
#define N 12010
using namespace std;
int a[N] , sum[N] , root[N] , c[N * 32][2] , si[N * 32] , tot , f[115][115];
inline void insert(int x , int &y , int v)
{
int i , u = y = ++tot;
bool t;
si[y] = si[x] + 1;
for(i = 1 << 30 ; i ; i >>= 1)
t = v & i , c[u][t] = ++tot , c[u][t ^ 1] = c[x][t ^ 1] , x = c[x][t] , u = c[u][t] , si[u] = si[x] + 1;
}
inline int query(int x , int y , int v)
{
int i , ans = 0;
bool t;
for(i = 1 << 30 ; i ; i >>= 1)
{
t = v & i;
if(si[c[x][t ^ 1]] == si[c[y][t ^ 1]]) x = c[x][t] , y = c[y][t];
else ans += i , x = c[x][t ^ 1] , y = c[y][t ^ 1];
}
return ans;
}
int main()
{
int n , m , i , j , k , b , l , r , x , y , ans = 0;
scanf("%d%d" , &n , &m);
for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]) , sum[i + 1] = sum[i] ^ a[i];
b = (int)sqrt(n + 1);
for(i = 1 ; i <= n + 1 ; i ++ ) insert(root[i - 1] , root[i] , sum[i]);
for(i = 1 ; i <= n / b + 1 ; i ++ )
{
for(j = i ; j <= n / b + 1 ; j ++ )
{
f[i][j] = f[i][j - 1];
for(k = (j - 1) * b + 1 ; k <= j * b && k <= n + 1 ; k ++ )
f[i][j] = max(f[i][j] , query(root[(i - 1) * b] , root[k] , sum[k]));
}
}
while(m -- )
{
scanf("%d%d" , &l , &r) , l = (l % n + ans % n) % n + 1 , r = (r % n + ans % n) % n + 1;
if(l > r) swap(l , r);
x = (l - 1) / b + 1 , y = (r ++ ) / b + 1 , ans = f[x + 1][y - 1];
if(x == y)
for(i = l ; i <= r ; i ++ )
ans = max(ans , query(root[l - 1] , root[r] , sum[i]));
else
{
for(i = l ; i <= x * b ; i ++ ) ans = max(ans , query(root[l - 1] , root[r] , sum[i]));
for(i = r ; i > (y - 1) * b ; i -- ) ans = max(ans , query(root[l - 1] , root[r] , sum[i]));
}
printf("%d\n" , ans);
}
return 0;
}
