题解 P5283 【[十二省联考2019]异或粽子】

可持久化$Trie$树+堆 刚开始想着在$Trie$树上二分来降一个$log$来着然后发现自己$sb$了 最开始的前缀和不用说了 然后我们可以用堆维护最大值，然后去扩展其它最大值，具体来讲，我们首先需要建一个可持久化$Trie$，滋磁区间$xor$最值查询，然后记录一个五元组$(l,r,val,ori,pos)$表示在区间$[l,r]$之间的某个数数与$ori$取异或最大为$val$且这个数的位置是$pos$，然后每次从堆里取$val$最大的然后分裂就行。 ```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 1000000007 #define mp std::make_pair #define eps 1e-4 #define mod 10086 #define lowbit(x) (x & -x) #define N 500005 #define ls (u << 1) #define rs (u << 1 | 1) #define cl(arr) memset(arr, 0, sizeof arr) #define bset std::bitset<N> inline void read (int &x) { x = 0; Re char ch = getchar(); while (!isdigit(ch)) ch = getchar(); while (isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); } struct trie { int rt[N], t[N * 33][2], cnt, sum[N * 33], id[N * 33]; inline void ins (int &uu, int pu, int val, int idx) { uu = ++cnt; int u = uu; sum[u] = sum[pu] + 1; fd (i, 31, 0) { bool now = (val >> i & 1); t[u][now] = ++cnt; t[u][!now] = t[pu][!now]; pu = t[pu][now]; u = t[u][now]; sum[u] = sum[pu] + 1; } id[u] = idx; } #define pi std::pair<ll, int> inline pi query (int u, int pu, int val) { pi ret = mp(0, 0); fd (i, 31, 0) { bool now = (val >> i & 1); if (sum[t[u][!now]] - sum[t[pu][!now]]) { ret.F |= 1ll << i; u = t[u][!now]; pu = t[pu][!now]; } else { u = t[u][now]; pu = t[pu][now]; } } ret.S = id[u]; return ret; } } t; unsigned int a[N]; int n, m; struct node { ll l, r, val, ori, pos; friend bool operator < (node x, node y) { return x.val < y.val; } }; std::priority_queue<node> q; int main () { scanf("%d %d", &n, &m); fo (i, 1, n) { scanf("%u", &a[i + 1]); a[i + 1] ^= a[i]; } ++n; fo (i, 1, n) t.ins(t.rt[i], t.rt[i - 1], a[i], i); fo (i, 1, n) { pi now = t.query(t.rt[i - 1], t.rt[0], a[i]); q.push((node) {1, i - 1, now.F, a[i], now.S}); } ll ans = 0; while (m--) { node u = q.top(); q.pop(); ans += u.val; if (u.l < u.pos) { pi now = t.query(t.rt[u.pos - 1], t.rt[u.l - 1], u.ori); q.push((node) {u.l, u.pos - 1, now.F, u.ori, now.S}); } if (u.pos < u.r) { pi now = t.query(t.rt[u.r], t.rt[u.pos], u.ori); q.push((node) {u.pos + 1, u.r, now.F, u.ori, now.S}); } } printf("%lld", ans); return 0; } ```