[BZOJ2741][[FOTILE模拟赛]][可持久化Trie+分块]
题目大意：
FOTILE得到了一个长为N的序列A，为了拯救地球，他希望知道某些区间内的最大的连续XOR和。 即对于一个询问，你需要求出Max(Ai⊕Ai+1⊕Ai+2...⊕Aj)，其中l≤i≤j≤r。 为了体现在线操作，对于一个询问(x,y)： l=Min(((x+lastans)%N)+1,((y+lastans)%N)+1) r=Max(((x+lastans)%N)+1,((y+lastans)%N)+1) 其中lastans是上次询问的答案，一开始为0。
思路：
首先我们维护一个异或前缀和序列A，A[i]=A[i−1]⊕a[i]，那么在[l,r]区间中找一段连续区间异或和最大就相当于在[l,r]中找两个正整数i,j求A[i]⊕A[j]最大。
然后我们对A数组分块，对于每块的第一个数A[i] 我们依次处理出对于所有的j≥i的[i,j]中的最大异或值 即s[i][j]=max(a[j]与i j所有数中的最大异或值,s[i][j−1])
所以对于每个询问[L,R]，先找出大于L的第一个分块点X，[X,R]的部分我们已经维护好了，剩下[L,X)的部分我们把每个数在可持久化Trie上查找。
复杂度是O((N+MM−−√)logN)。
坑：
这道题Hint里面写每个数的范围在longint范围内，结果开了int64内存炸了，然后发现好像这是针对pas选手的。。。C++只用开int就行了。
然后是最最最坑的地方：
本题的强制在线如果直接加会爆int导致调用数组下标为负
这就是我一直RE的原因。。。。。
技巧：
在一个数组前面开一个变量可以让数组取到−1，当然不开也是可以的，但鬼知道会访问到哪块内存。
代码：
#include <bits/stdc++.h>using namespace std; const int Maxn = 13000;inline int Max(const int &a, const int &b) { return a > b ? a : b;}inline int Min(const int &a, const int &b) { return a < b ? a : b;}namespace IO { inline char get(void) { static char buf[1000000], *p1 = buf, *p2 = buf; if (p1 == p2) { p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin); if (p1 == p2) return EOF; } return *p1++; } inline void read(int &x) { x = 0; static char c; bool f = 0; for (; !(c >= '0' && c <= '9'); c = get()) if (c == '-') f = 1; for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = get()); if (f) x = -x; } inline void write(int x) { if (!x) return (void)puts("0"); if (x < 0) putchar('-'), x = -x; static short s[12], t; while (x) s[++t] = x % 10, x /= 10; while (t) putchar('0' + s[t--]); putchar('/n'); }};int FFF;int root[Maxn], a[Maxn], sum[Maxn], b[Maxn];int n, m;struct Trie { int cnt; int ch[Maxn << 5][2], sum[Maxn << 5]; inline int insert(int x, int val) { int tmp, y; tmp = y = ++cnt; for (int i = 30; i >= 0; i--) { ch[y][0] = ch[x][0]; ch[y][1] = ch[x][1]; sum[y] = sum[x] + 1; int t = (val & b[i]) >> i; x = ch[x][t]; ch[y][t] = ++cnt; y = ch[y][t]; } sum[y] = sum[x] + 1; return tmp; } inline int query(int l, int r, int val) { int tmp = 0; for (int i = 30; i >= 0; i--) { int t = (val & b[i]) >> i; if (sum[ch[r][t ^ 1]] - sum[ch[l][t ^ 1]]) tmp += b[i], r = ch[r][t ^ 1], l = ch[l][t ^ 1]; else r = ch[r][t], l = ch[l][t]; } return tmp; }} trie;int block, ans, s[501][Maxn];int main(void) { //freopen("in.txt", "r", stdin); IO::read(n), IO::read(m); b[0] = 1; for (int i = 1; i <= 30; i++) b[i] = b[i - 1] << 1; for (int i = 1; i <= n; i++) IO::read(a[i]); for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] ^ a[i]; for (int i = 0; i <= n; i++) root[i] = trie.insert(root[i - 1], sum[i]); block = sqrt(n + 1); for (int i = 0; i * block <= n; i++) { for (int j = i * block; j <= n; j++) { s[i][j] = Max(trie.query(root[i * block - 1], root[j], sum[j]), j ? s[i][j - 1] : 0); } } int x, y, l, r; while (m--) { IO::read(x), IO::read(y); l = ((long long)x + ans) % n + 1; r = ((long long)y + ans) % n + 1; if (l > r) swap(l, r); l--; int tmp = l / block + 1; ans = s[tmp][r]; for (tmp = Min(tmp * block - 1, r); tmp >= l; --tmp) { ans = Max(ans, trie.query(root[l - 1], root[r], sum[tmp])); } IO::write(ans); } return 0;}完。
By g1n0st
