首页 > 代码库 > BZOJ3261 最大异或和
BZOJ3261 最大异或和
这是是一道可持久化数据结构题。具体分类不明
按二进制位建立一颗可持久化树：
因为每个节点都有两个儿子，于是非常像线段树，但是其实本质又是trie，于是就叫它可持久化trie吧。。。
每次新家点的时候就在trie里加一条链，然后查询用贪心方法查即可。
1 /************************************************************** 2 Problem: 3261 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:4168 ms 7 Memory:191432 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <cstring>12 #include <algorithm>13 14 using namespace std;15 16 struct trie_node{17 int sum, son[2];18 } tr[16000000];19 20 int n, m, last, tot, root[800000];21 22 void ins(int x, int &y, int V, int D){23 y = ++tot, tr[y].sum = tr[x].sum + 1;24 if (D < 0) return;25 int p = (V >> D) & 1;26 tr[y].son[p ^ 1] = tr[x].son[p ^ 1];27 ins(tr[x].son[p], tr[y].son[p], V, D - 1);28 }29 30 int query(int x, int y, int V, int D){31 if (D < 0) return 0;32 int p = (V >> D) & 1;33 if (tr[tr[x].son[p ^ 1]].sum == tr[tr[y].son[p ^ 1]].sum)34 return query(tr[x].son[p], tr[y].son[p], V, D - 1);35 else return query(tr[x].son[p ^ 1], tr[y].son[p ^ 1], V, D - 1) + (1 << D);36 }37 38 int main(){ 39 scanf("%d%d", &n, &m);40 int L, R, X;41 ++n, tot = 0;42 tr[0].son[0] = tr[0].son[1] = tr[0].sum = 0;43 ins(root[0], root[1], 0, 24);44 last = 0;45 for (int i = 2; i <= n; ++i){46 scanf("%d", &X);47 ins(root[i - 1], root[i], last ^= X, 24);48 }49 50 char CH;51 while (m--){52 scanf("\n%c", &CH);53 if (CH == ‘A‘){54 scanf("%d", &X), ++n;55 ins(root[n - 1], root[n], last ^= X, 24);56 } else{57 scanf("%d%d%d", &L, &R, &X);58 printf("%d\n", query(root[L - 1], root[R], last ^ X, 24));59 }60 }61 return 0;62 }
p.s. AC100纪念（虽然好多好多水题。。>.<）
BZOJ3261 最大异或和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。