给出一个长度为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 思路：
可持久化Trie树模板题，不加输入输出是优化也可以过，加了会减很多耗时，之前数组开小了，超时了好几发。
参考博客：
https://www.cnblogs.com/RabbitHu/p/51nod1295.html
实现代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 1e5+;
int a[M];
int rt[M]={},siz[M<<],son[M<<][],idx;
template <class T>
void read(T &x){
char c;
bool op = ;
while(c = getchar(), c < '' || c > '')
if(c == '-') op = ;
x = c - '';
while(c = getchar(), c >= '' && c <= '')
x = x * + c - '';
if(op) x = -x;
}
template <class T>
void write(T x){
if(x < ) putchar('-'), x = -x;
if(x >= ) write(x / );
putchar('' + x % );
} void Insert(int i,int x){
int now = rt[i] = ++idx;
int old = rt[i-];
for(int i = ;i >= ;i --){
siz[now] = siz[old] + ;
if((x >> i)& ) son[now][] = son[old][],son[now][] = ++idx;
else son[now][] = son[old][],son[now][] = ++idx;
now = son[now][(x>>i)&];
old = son[old][(x>>i)&];
}
siz[now] = siz[old] + ;
} int query(int l,int r,int x){
int now = rt[r],old = rt[l],ans = ;
for(int i = ;i >= ;i --){
int dir = (x >> i)&;
int delta_siz = siz[son[now][!dir]] - siz[son[old][!dir]];
if(delta_siz) now = son[now][!dir],old = son[old][!dir],ans = ans << |;
else now = son[now][dir],old = son[old][dir],ans = ans << ;
}
return ans;
} int main(){
int n,q,l,r,x;
idx = ;
read(n);read(q);
for(int i = ;i <= n;i ++){
read(a[i]);
}
for(int i = ;i <= n;i ++)
Insert(i,a[i]);
while(q--){
read(x);read(l);read(r);
write(query(l,r+,x));
putchar('\n');
}
return ;
}