Description
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 ).
r = max ( ((x+lastans) mod N)+1 , ((y+lastans) mod N)+1 ).
其中lastans是上次询问的答案，一开始为0。
Input
第一行两个整数N和M。
第二行有N个正整数，其中第i个数为Ai，有多余空格。
后M行每行两个数x,y表示一对询问。
Output
共M行，第i行一个正整数表示第i个询问的结果。
Sample Input
3 3
1 4 3
0 1
0 1
4 3
1 4 3
0 1
0 1
4 3
Sample Output
5
7
7
7
7
HINT
HINT
N=12000，M=6000，x,y,Ai在signed longint范围内。
Source
【分析】
第一次写可持久化trie，还有点问题。
题解网上都是...先不说了
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <utility>
#include <iomanip>
#include <string>
#include <cmath>
#include <queue>
#include <assert.h>
#include <map> const int N = + ;
const int SIZE = ;//块状链表的根号50000
const int M = + ;
using namespace std;
typedef long long ll;
struct Node{
int val;//代表数量
int num;//代表值
Node *ch[];
}mem[N * * ], *root[N];
int n, m;//n为数量,m为操作次数
struct BLOCK_LIST{//块状链表
int data[SIZE];
int size, next;
void init(){
size = ;
memset(data, , sizeof(data));
next = -;
}
}list[SIZE];
int tot = ;//记录mem使用空间
int Max[SIZE + ][SIZE + ], Pos;//表示从i到j块的最大异或值
int data[N]; Node *NEW(){//创建新trie节点
Node *p = &mem[tot++];
p->val = p->num = ;
p->ch[] = p->ch[] = NULL;
return p;
}
void insert(Node *&p, Node *&last, int x){//k为根
p = NEW(); Node *u = p, *a = last;
for (int i = ; i >= ; i--){
int t = ((( << i) & x) == ? : );
if (u->ch[t] == NULL){
u->ch[t] = NEW();
u->ch[t]->val = t;
u->ch[t]->num = a->ch[t]->num + ;
}
u->ch[t ^ ] = a -> ch[t ^ ];
u = u -> ch[t];
a = a -> ch[t];
}
return;
}
int find(Node *&a, Node *&b, int val){
int Ans = ;
Node *x = a, *y = b;
for (int i = ; i >= ; i--){ int t = (((( << i) & val) == ? : ) ^ );
if (x->ch[t] == NULL || (x->ch[t]->num - y->ch[t]->num) <= ) t = (t ^ );
Ans += ( << i) * t;
x = x->ch[t];
y = y->ch[t];
}
//Ans += t;
return Ans;
} void prepare(){
memset(Max, , sizeof( Max ));
Pos = ;//Pos为块状链表的标号
list[Pos++].init();
insert(root[], root[], );//插入可持久化trie
for (int cur = , i = ; i <= n; cur = list[cur].next){
int j, M = ;//M用来记录块的最大值
for (j = ; j < SIZE && i <= n; i++, j++){
list[cur].data[j] = data[i];
list[cur].size++;
insert(root[i + ], root[i], data[i]);//插入可持久化trie
int M2 = data[i];
//M2 = find(root[i + 1], root[cur * SIZE], list[cur].data[j]);
//printf("%d\n", M2);
//if (M2 == data[i]) M2 = 0;//显然如果是它自己不如不加即直接从开头一直异或到i
//Max[cur][cur] = M2;
for (int k = Pos - ; k >= ; k--){
int tmp = find(root[i + ], root[k * SIZE], data[i]);
//if (tmp == data[i]) tmp = 0;
if ((M2 ^ data[i]) < (tmp ^ data[i])) M2 = tmp;
Max[k][cur] = max(Max[k][cur], M2 ^ data[i]);//顺便利用O(sqrt(n))的时间预处理出Max数组
}
}
//创建新块
if (j == SIZE){
list[Pos].init();
list[cur].next = Pos++;
}
}
//printf("%d\n", root[1]->ch[0]->ch[1]->num);
}
int query(int l, int r){
int x = (l - ) / SIZE, y = (r - ) / SIZE;//x代表l和r所代表的块
int Ans = ;
if (x == y){
for (int i = l; i <= r; i++)
Ans = max(Ans, find(root[r + ], root[l - ], data[i]) ^ data[i]);
return Ans;
}else{
if (x <= y - ) Ans = Max[x ][y - ];
//for (int i = r; i >= l; i--) if ((data[i] ^ data[i - 1]) == 32767) printf("fuck");
for (int i = l; i <= ((x + ) * SIZE) && i <= n; i++) Ans = max(Ans, find(root[r + ], root[l - ], data[i]) ^ data[i]);
for (int i = r; i > y * SIZE; i--) Ans = max(Ans, find(root[r + ], root[l - ], data[i]) ^ data[i]);
return Ans;
//for (int i = l; i <= r; i++)
// Ans = max(Ans, find(root[r + 1], root[l - 1], data[i]) ^ data[i]);
//return Ans;
}
}
//处理询问
void work(){
int last_ans = ;
for (int i = ; i <= m; i++){
int x, y, l, r;
scanf("%d%d", &l, &r);
//l--;
//l = min(((ll)((ll)x + (ll)last_ans) % n) + 1 , ((ll)((ll)y + (ll)last_ans) % n)+ 1);
//r = max(((ll)((ll)x + (ll)last_ans) % n) + 1 , ((ll)((ll)y + (ll)last_ans) % n)+ 1);
last_ans = query(l, r);
printf("%d\n", last_ans);
}
}
//单纯的插入一个数
void build(Node *&b, int x){
Node *u = b;
for (int i = ; i >= ; i--){
int t = ((( << i) & x) == ? : );//表示这一位是否是0
if (u->ch[t] == NULL){
u->ch[t] = NEW();
u->ch[t]->val = t;
u->ch[t]->num = ;//注意，这里仅仅只是建树，所以不能改数字
}
u = u->ch[t];
}
return;
}
void init(){
//读入+建初始树
scanf("%d%d", &n, &m);
for (int i = ; i < N; i++) root[i] = NULL;
root[] = NEW();
data[] = ;
for (int i = ; i <= n; i++){
scanf("%d", &data[i]);
data[i] = data[i] ^ data[i - ];
build(root[], data[i]);
//printf("%d\n", data[i]);
}
build(root[], );//记得加0
//printf("%d", root[0]->val);
}
void debug(){
insert(root[], root[], );
insert(root[], root[], );
insert(root[], root[], );
printf("%d\n", find(root[], root[], ));
} int main(){
#ifdef LOCAL
freopen("data.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
init();
prepare();
work();
printf("%d\n", tot);
//debug();
return ;
}