Jim是一个热爱打游戏的小伙子，可惜他的游戏水平不太行，以至于经常在游戏里被别人欺负。而且Jim不仅游戏玩的菜，他还很爱喷人，但是由于自己的垃圾操作，他又喷不过别人。为了改善这种局面，Jim决定成为一个腿部挂件（俗称抱大腿）。 已知现在有N个选手可供Jim选择，每位选手的能力值为 ai。N位选手不一定每位选手都有时间配Jim玩游戏而且Jim的状态也时好时坏，所以Jim有Q个询问，每个询问是3个数X、L、R，求第L个人到第R个人这R-L+1个人中与Jim配合后的能力值最大是多少，Jim 与第i位选手配合后的能力值为ai与X进行异或运算（Xor）。
第1行：2个数N, Q中间用空格分隔，分别表示选手个数及查询的数量(1≤N≤200000,1≤Q≤200000)。 第2 行：共N个数为每个选手能力值中间用空格分隔，对应ai(0≤a[i]≤10^9)。 第N+2 - N+Q+1行：每行3个数X, L, R，中间用空格分隔。（0≤X≤10^9，0≤L≤R<N)
输出共Q行，对应每次询问所能得到的最大能力值。
对于第一个询问 2 与{4 12 0} 最大的能力值组合为 2 xor 12 = 14 注意 L R标号从 0 开始 对于20%的数据保证 (1≤N≤5000, 1≤Q≤5000)。 对于45%的数据保证 (1≤N≤50000, 1≤Q≤50000)。 对于100%的数据保证 (1≤N≤200000, 1≤Q≤200000)。
题目大意：给出n个数，在给出m个查询，每次查询的形式是x,l,r，输出在闭区间[l,r]内与x异或后最大的结果
题目分析：这个题如果是按点给分制的题目，我们完全可以暴力跑过数据比较水的测试点，但当n和m比较大的时候，n*n的暴力就显然无法通过所有测试点了，因为之前学了一波如何线性查找任意两个数异或的最大值，知道了字典树可以处理异或最大值或最小值的问题，这个题也是那种问题的进阶版，因为涉及到了区间，所以也就需要将字典树可持久化，那么这个题目的正解也就是可持久化01字典树，构造完字典树后对应输出即可，第一次接触，挂个板子，以后若有需要再深入学习
代码：
#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std; typedef long long LL; const int inf=0x3f3f3f3f; const int N=2e5+100; int trie[N*32][2]; int sum[N*32]; int root[N]; int cnt=1;//这里注意一定要从1开始，因为所有trie的初始化为0，如果第0号节点设上数了，会对后续节点产生影响 void insert(int pre,int& cur,int step,int x) { cur=cnt++;//新建一个版本 trie[cur][0]=trie[pre][0]; trie[cur][1]=trie[pre][1];//复制前一个节点的信息 sum[cur]=sum[pre]+1;//加上当前新建的链 if(step<0)//x到最后一位了 return; int to=(x>>step)&1;//提取出x的当前位 insert(trie[pre][to],trie[cur][to],step-1,x);//递归建树 } int search(int l,int r,int step,int x) { if(step<0) return 0; int to=(x>>step)&1; if(sum[trie[r][!to]]>sum[trie[l][!to]])//说明有可以异或的这条路 return search(trie[l][!to],trie[r][!to],step-1,x)+(1<<step); else return search(trie[l][to],trie[r][to],step-1,x); } int main() { // freopen("input.txt","r",stdin); int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { int num; scanf("%d",&num); insert(root[i-1],root[i],30,num); } while(m--) { int l,r,x; scanf("%d%d%d",&x,&l,&r); l++,r++; printf("%d\n",search(root[l-1],root[r],30,x)); } return 0; }
