题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1295
收藏
关注给出一个长度为N的正整数数组A，再给出Q个查询，每个查询包括3个数，L, R, X (L <= R)。求A[L] 至 A[R] 这R - L + 1个数中，与X 进行异或运算(Xor)，得到的最大值是多少？
Input
第1行：2个数N, Q中间用空格分隔，分别表示数组的长度及查询的数量(1 <= N <= 50000, 1 <= Q <= 50000)。
第2 - N+1行：每行1个数，对应数组A的元素(0 <= A[i] <= 10^9)。
第N+2 - N+Q+1行：每行3个数X, L, R，中间用空格分隔。（0 <= X <= 10^9，0 <= L <= R < N)
Output
输出共Q行，对应数组A的区间[L,R]中的数与X进行异或运算，所能得到的最大值。
Input示例
15 8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
10 5 9
1023 6 6
33 4 7
182 4 9
181 0 12
5 9 14
99 7 8
33 9 13
Output示例
13
1016
41
191
191
15
107
47
题解：
1.此题（HDU4825 Xor Sum）的加强版
2.由于要求的是x与区间[l,r]的某个数异或值最大，所以在Trie树的基础上，可以模仿可持久化线段树，建立一棵可持久化Trie树。这样就可以得到每插入一个数时的历史版本的Trie树。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+;
const int MAXN = 1e5+; struct Trie
{
int end[*MAXN], next[*MAXN][];
int root[MAXN], L = ;
int newnode()
{
next[L][] = next[L][] = -;
end[L++] = ;
return L-;
}
void init()
{
L = ;
}
void build(LL val) //初始化版本
{
int tmp = root[];
for(int i = ; i>=; i--)
{
int way = (val>>i)&;
if(next[tmp][way]==-) next[tmp][way] = newnode();
tmp = next[tmp][way];
}
}
int insert(int preroot, LL val)
{
int newroot = newnode(), rootbuf = newroot;
for(int i = ; i>=; i--)
{
int way = (val>>i)&;
next[newroot][way] = newnode(); //要走的路，新开出来
next[newroot][!way] = next[preroot][!way]; //另一条路，指向上一个历史版本的 newroot = next[newroot][way];
preroot = next[preroot][way];
end[newroot] = end[preroot]+; //叠加
}
return rootbuf;
}
LL query(int Lroot, int Rroot, LL val)
{
LL ret = ;
for(int i = ; i>=; i--)
{
ret <<= ;
int way = (val>>i)&;
if(next[Lroot][!way]!=- && (end[next[Rroot][!way]]-end[next[Lroot][!way]]>))
{
ret ^= ;
Lroot = next[Lroot][!way];
Rroot = next[Rroot][!way];
}
else
{
Lroot = next[Lroot][way];
Rroot = next[Rroot][way];
}
}
return ret;
}
};
Trie T; LL a[MAXN];
int main()
{
int n, q;
while(scanf("%d%d",&n,&q)!=EOF)
{
T.init();
T.root[] = T.newnode();
for(int i = ; i<=n; i++) //建立初始化版本
{
scanf("%lld",&a[i]);
T.build(a[i]);
}
for(int i = ; i<=n; i++) //每插入一个数，就生成一个历史版本的Trie树
T.root[i] = T.insert(T.root[i-],a[i]); while(q--)
{
int x, l, r;
scanf("%d%d%d",&x,&l,&r);
l++; r++;
printf("%lld\n", T.query(T.root[l-],T.root[r],1LL*x));
}
}
}