51nod 1295 XOR key-区间异或最大值-可持久化01Trie树(模板)
1295 XOR key[*]2 秒
[*]262,144 KB
[*]160 分
[*]6 级题
给出一个长度为N的正整数数组A，再给出Q个查询，每个查询包括3个数，L, R, X (L <= R)。求A 至 A 这R - L + 1个数中，与X 进行异或运算(Xor)，得到的最大值是多少？
收起
输入第1行：2个数N, Q中间用空格分隔，分别表示数组的长度及查询的数量(1 <= N <= 50000, 1 <= Q <= 50000)。
第2 - N+1行：每行1个数，对应数组A的元素(0 <= A <= 10^9)。
第N+2 - N+Q+1行：每行3个数X, L, R，中间用空格分隔。（0 <= X <= 10^9，0 <= L <= R < N)
输出输出共Q行，对应数组A的区间中的数与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----------------------------------------------------------
今天闲来无事看了一下，突然发现懂了，可能以前傻了，改了一下代码，以前写的有点丑。。。
直接贴代码：
代码：
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn=1e5+10;
5
6 int son,sum,root,sz=0;
7 //son每个节点指向的两个节点的位置，sum每个节点出现的次数，root每棵01Trie根节点的位置
8
9 void insert(int val,int &x,int pre)
10 {
11 x=++sz;int t=x;//新建一个版本
12 for(int i=31;i>=0;i--){
13 son=son;son=son;//当前版本的Trie节点指向前一个Trie版本的节点，复制，节省空间
14 sum=sum+1;
15 int j=(val>>i)&1;
16 son=++sz;//新开的节点
17 t=son;pre=son;
18 }
19 sum=sum+1;
20 }
21
22 int query(int val,int x,int y)
23 {
24 int ans=0;
25 for(int i=31;i>=0;i--){
26 int j=(val>>i)&1;
27 if(sum]-sum]>0){//说明比之前的版本大
28 ans|=(1<<i);//当前位两者异或一定为1,找最大值嘛
29 x=son;y=son;
30 }
31 else{
32 x=son;y=son;
33 }
34 }
35 return ans;
36 }
37
38 int main()
39 {
40 int n,m,x;
41 cin>>n>>m;
42 for(int i=1;i<=n;i++){
43 cin>>x;
44 insert(x,root,root);//以元素下标作为版本号
45 }
46 while(m--){
47 int l,r;
48 cin>>x>>l>>r;
49 l++;r++;
50 cout<<query(x,root,root)<<endl;
51 }
52 return 0;
53 }
文档来源：51CTO技术博客https://blog.51cto.com/u_15310764/3168000
页:
[1]