1295 XOR key
- 2 秒
- 262,144 KB
- 160 分
- 6 级题
给出一个长度为N的正整数数组A，再给出Q个查询，每个查询包括3个数，L, R, X (L <= R)。求A[L] 至 A[R] 这R - L + 1个数中，与X 进行异或运算(Xor)，得到的最大值是多少？
收起
输入
第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)
输出
输出共Q行，对应数组A的区间[L,R]中的数与X进行异或运算，所能得到的最大值。
输入样例
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
输出样例
13
1016
41
191
191
15
107
47
Trie树的模板题，Trie树处理区间异或查值问题，一直都不会这种区间查找异或值的最大值，发现是可持久化Trie树，打扰了。
每个数建31个树，然后查询的时候从高位到低位找就OK了。
Trie树原理很好理解，5分钟就可以懂，但是代码我看的时候，不同版本虽然实现的功能是相同的，但是还是有差别的，输出来中间过程也没看懂，但是能想懂，就是和代码对不上。。。。打扰了。
多练习就好啦。
--------------------------------------------------------2019.2.19----------------------------------------------------------
今天闲来无事看了一下，突然发现懂了，可能以前傻了，改了一下代码，以前写的有点丑。。。
直接贴代码：
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+; int son[maxn<<][],sum[maxn<<],root[maxn],sz=;
//son每个节点指向的两个节点的位置，sum每个节点出现的次数，root每棵01Trie根节点的位置 void insert(int val,int &x,int pre)
{
x=++sz;int t=x;//新建一个版本
for(int i=;i>=;i--){
son[t][]=son[pre][];son[t][]=son[pre][];//当前版本的Trie节点指向前一个Trie版本的节点，复制，节省空间
sum[t]=sum[pre]+;
int j=(val>>i)&;
son[t][j]=++sz;//新开的节点
t=son[t][j];pre=son[pre][j];
}
sum[t]=sum[pre]+;
} int query(int val,int x,int y)
{
int ans=;
for(int i=;i>=;i--){
int j=(val>>i)&;
if(sum[son[y][j^]]-sum[son[x][j^]]>){//说明比之前的版本大
ans|=(<<i);//当前位两者异或一定为1,找最大值嘛
x=son[x][j^];y=son[y][j^];
}
else{
x=son[x][j];y=son[y][j];
}
}
return ans;
} int main()
{
int n,m,x;
cin>>n>>m;
for(int i=;i<=n;i++){
cin>>x;
insert(x,root[i],root[i-]);//以元素下标作为版本号
}
while(m--){
int l,r;
cin>>x>>l>>r;
l++;r++;
cout<<query(x,root[l-],root[r])<<endl;
}
return ;
}