搞成前缀和然后就可以很方便地用可持久化trie维护了.时间复杂度O((N+M)*25)
-------------------------------------------------------------------------
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
#define b(x) (1 << (x))
#define Rt(x) Root[(x) + 1]
const int maxn = 600009;
const int Log = 25;
int N, M, TOT;
int w[maxn];
inline int read() {
char c = getchar();
for(; !isdigit(c); c = getchar());
int ret = 0;
for(; isdigit(c); c = getchar())
ret = ret * 10 + c - '0';
return ret;
}
struct Node {
Node* ch[2];
int cnt;
Node() : cnt(0) {
}
} pool[maxn * Log], *pt, *Root[maxn], *Null;
void Init_Trie() {
pt = pool;
Null = pt++;
Null->ch[0] = Null->ch[1] = Null;
}
Node* Insert(Node* t, int Val, int w) {
Node* h = pt++;
h->cnt = t->cnt + 1;
if(w < 0) return h;
int v = Val & b(w) ? 1 : 0;
h->ch[v ^ 1] = t->ch[v ^ 1];
h->ch[v] = Insert(t->ch[v], Val, w - 1);
return h;
}
int Query(Node* L, Node* R, int Val) {
int ret = 0;
for(int i = Log; i >= 0; i--) {
int v = Val & b(i) ? 1 : 0;
if(R->ch[v ^ 1]->cnt > L->ch[v ^ 1]->cnt) {
ret |= b(i);
L = L->ch[v ^ 1];
R = R->ch[v ^ 1];
} else
L = L->ch[v], R = R->ch[v];
}
return ret;
}
void Init() {
Init_Trie();
Root[0] = Null;
Rt(0) = Insert(Root[0], 0, Log);
N = read(); M = read();
w[0] = 0;
for(int i = 1; i <= N; i++)
Rt(i) = Insert(Rt(i - 1), w[i] = read() ^ w[i - 1], Log);
TOT = w[N];
}
void Solve() {
while(M--) {
char c; scanf(" %c", &c);
if(c == 'A') {
w[++N] = read();
w[N] ^= w[N - 1];
Rt(N) = Insert(Rt(N - 1), TOT = w[N], Log);
} else {
int l = read() - 2, r = read() - 1, x = read();
x ^= TOT;
printf("%d\n", Query(Rt(l), Rt(r), x));
}
}
}
int main() {
Init();
Solve();
return 0;
}
-------------------------------------------------------------------------
3261: 最大异或和
Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 946 Solved: 398
[Submit][Status][Discuss]
Description
给定一个非负整数序列 {a}，初始长度为 N。
有 M个操作，有以下两种操作类型：
1 、A x：添加操作，表示在序列末尾添加一个数 x，序列的长度 N+1。
2 、Q l r x：询问操作，你需要找到一个位置 p，满足 l<=p<=r，使得：
a[p] xor a[p+1] xor ... xor a[N] xor x 最大，输出最大是多少。
Input
第一行包含两个整数 N ，M，含义如问题描述所示。
第二行包含 N个非负整数，表示初始的序列 A 。
接下来 M行，每行描述一个操作，格式如题面所述。
Output
假设询问操作有 T个，则输出应该有 T行，每行一个整数表示询问的答案。
Sample Input
5 5
2 6 4 3 6
A 1
Q 3 5 4
A 4
Q 5 7 0
Q 3 6 6
对于测试点 1-2，N,M<=5 。
2 6 4 3 6
A 1
Q 3 5 4
A 4
Q 5 7 0
Q 3 6 6
对于测试点 1-2，N,M<=5 。
对于测试点 3-7，N,M<=80000 。
对于测试点 8-10，N,M<=300000 。
其中测试点 1, 3, 5, 7, 9保证没有修改操作。
对于 100% 的数据， 0<=a[i]<=10^7。
Sample Output
4
5
6
5
6
HINT
对于 100% 的数据， 0<=a[i]<=10^7 。