给出一个长度为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 12345678910111213141510 5 91023 6 633 4 7182 4 9181 0 125 9 1499 7 833 9 13
输出样例
13 1016 41 191 191 15 107 47
Trie树的模板题,Trie树处理区间异或查值问题,一直都不会这种区间查找异或值的最大值,发现是可持久化Trie树,打扰了。
每个数建31个树,然后查询的时候从高位到低位找就OK了。
Trie树原理很好理解,5分钟就可以懂,但是代码我看的时候,不同版本虽然实现的功能是相同的,但是还是有差别的,输出来中间过程也没看懂,但是能想懂,就是和代码对不上。。。。打扰了。
多练习就好啦。
--------------------------------------------------------2019.2.19----------------------------------------------------------
今天闲来无事看了一下,突然发现懂了,可能以前傻了,改了一下代码,以前写的有点丑。。。
直接贴代码:
代码:
1 #include2 using namespace std; 3 typedef long long ll; 4 const int maxn=1e5+10; 5 6 int son[maxn<<5][2],sum[maxn<<5],root[maxn],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[t][0]=son[pre][0];son[t][1]=son[pre][1];//当前版本的Trie节点指向前一个Trie版本的节点,复制,节省空间14 sum[t]=sum[pre]+1;15 int j=(val>>i)&1;16 son[t][j]=++sz;//新开的节点17 t=son[t][j];pre=son[pre][j];18 }19 sum[t]=sum[pre]+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[son[y][j^1]]-sum[son[x][j^1]]>0){ //说明比之前的版本大28 ans|=(1< >n>>m;42 for(int i=1;i<=n;i++){43 cin>>x;44 insert(x,root[i],root[i-1]);//以元素下标作为版本号45 }46 while(m--){47 int l,r;48 cin>>x>>l>>r;49 l++;r++;50 cout< <