题解 P4735 【最大异或和】

可持久化Trie板子题 如果你会主席树的话，我有自信几句话就讲清楚这个算法 如果你不会的话，还是去学学主席树吧。 你肯定是会01trie的，但是01trie加进去就无序了，想想主席树，我们可以将每一次加数都新建一条链，那样就相当于又建了一棵01trie，n个数就会出现n个01trie，然后你有左端点和右端点，记录一下每个点的sum值，接下来就是主席树基操了。 warning:这题卡常，我开O2 ```cpp #include<bits/stdc++.h> #define Re register #define fo(i, a, b) for (Re int i = (a); i <= (b); ++i) #define fd(i, a, b) for (Re int i = (a); i >= (b); --i) #define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v) #define pb push_back #define F first #define S second #define ll long long #define inf 10000000000007 #define mp std::make_pair #define lowbit(x) (x & -x) #define mod 19260817 #define eps 1e-4 #define itset std::set<node>::iterator #define lb lower_bound #define N 18000005 #define ls (k << 1) #define rs (k << 1 | 1) char ch; int b[N], rt[N], t[N][2], sum[N]; int n, m, s, x, cnt, l, r; inline void split (int x) { fo (i, 0, 24) { if (x & 1) b[i] = 1; else b[i] = 0; x >>= 1; } } inline void update (int &now, int pk) { now = ++cnt; int k = now; sum[k] = sum[pk] + 1; fd (i, 24, 0) { t[k][b[i]] = ++cnt; t[k][b[i] ^ 1] = t[pk][b[i] ^ 1]; k = t[k][b[i]]; pk = t[pk][b[i]]; sum[k] = sum[pk] + 1; } } inline int query (int pk, int k) { int ret = 0; fd (i, 24, 0) { ret <<= 1; if (sum[t[k][b[i] ^ 1]] - sum[t[pk][b[i] ^ 1]] > 0) { ret |= 1; k = t[k][b[i] ^ 1]; pk = t[pk][b[i] ^ 1]; } else { k = t[k][b[i]]; pk = t[pk][b[i]]; } } return ret; } int main () { scanf("%d %d", &n, &m); ++n; update(rt[1], rt[0]); fo (i, 2, n) { scanf("%d", &x); s ^= x; split(s); update(rt[i], rt[i - 1]); } fo (i, 1, m) { ch = getchar(); while (ch != 'A' && ch != 'Q') ch = getchar(); if (ch == 'A') { ++n; scanf("%d", &x); s ^= x; split(s); update(rt[n], rt[n - 1]); } else { scanf("%d %d %d", &l, &r, &x); split(s ^ x); printf("%d\n", query(rt[l - 1], rt[r])); } } return 0; } ```