问题 A: 腿部挂件 时间限制: 2 Sec 内存限制: 256 MB 题目描述
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行，对应每次询问所能得到的最大能力值。
样例输入
9 8 2 15 4 12 0 6 0 16 12 2 2 5 4 8 8 16 5 8 16 6 8 1 0 5 12 3 4 15 1 1 5 0 4
样例输出
14 8 28 28 14 12 0 10
提示
对于第一个询问 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)。
读完这个题，显然是用一个可持续化的Tire树，这是我当时意淫出来的东西，一看蓝皮书，woc真的有。那就学一下喽。我自己尝试实现，到最后遇到了点困难，只好看书上的板子了。 类比主席树，每次插入词语时，不能在原点上覆盖，必须另外开点。理解起来还是比较容易的，蓝皮书上维护的是每个节点的最后一次经过的值。和我意淫出来的不太一样（我想的是维护次数，每次两个端点值相减如果不等于零，说明该区间内有这个值。不过显然是蓝皮书上比较的容易）。
更新：第二天一早看一下？？被hack了？？运行错误？怎么可能，开的2e5，树节点开到32倍，怎么会？？带疑惑开了4e5.遂过。。 下面是ac代码（from 蓝皮书）：
#include <iostream> #include <cstring> #include <string> #include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <queue> #include <map> #include <set> #define ll long long using namespace std; const int N = 4e5+5; int tr[N<<5][2], latest[N<<5]; int s[N], root[N], n, m, tot; void insert(int i, int k, int p, int q)//以tr[p]为范本在tr[q]插入s[i]的第k位。 { if (k < 0)//插完 { latest[q] = i;//更新结束点最新经过时间 return; } int c = s[i] >> k & 1; if (p) tr[q][c^1] = tr[p][c^1]//不变的孩子直接连边旧点; tr[q][c] = ++tot;//变的孩子开新点存储 insert(i, k-1, tr[p][c], tr[q][c]); latest[q] = max(latest[tr[q][0]], latest[tr[q][1]]);//向上更新。 } int ask(int now, int val, int k, int limit) { if (k < 0) return s[latest[now]]^val;//ask完毕 int c = val >> k & 1; if (latest[tr[now][c^1]] >= limit)//优先检索相反的孩子 return ask(tr[now][c^1], val, k-1, limit); else return ask(tr[now][c], val, k-1, limit); } int main() { scanf("%d%d", &n, &m); latest[0] = -1; root[0] = ++tot; insert(0, 31, 0, root[0]);//建立空树 for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); s[i] = x; root[i] = ++tot; insert(i, 31, root[i-1], root[i]); } for (int i = 1; i <= m; i++) { int x, l, r; scanf("%d%d%d", &x, &l, &r); printf("%d\n", ask(root[r+1], x, 31, l+1)); } return 0; }