[十二省联考2019] 异或粽子

阳光穿透心脏的1/2处 2021-12-14 10:45 431阅读 0赞

### \[十二省联考2019\] 异或粽子 ###

#### 题意: ####

[题目传送门][Link 1]

#### 题解： ####

没有做过[异或之][Link 2]和[超级钢琴][Link 3]，但是这几道题的做法似乎还是非常好想的。首先做前缀异或和，这样问题转化成了个给定序列，找出\$K\$对数字对\$(i, j)\$使这几对数字的异或的值之和最大。考虑如果我们确定右端点\$r\$，那么异或最大值是很好确定的，直接在\$Trie\$上查找即可。假如我们要查找第\$K\$大的异或值的话，就可以使用可持久化\$Trie\$树。虽然以前没有写过，但写法就和主席树差不多。每当找到\$r\$为右端点的最大值之后，把这个异或值删除，再次查找的就是第二大的了，以此类推就可以得到第\$K\$大的了。

然后我们用堆维护每一个点为右端点时的异或最大值，然后每次取出堆顶的值，更新次大值即可。总共会修改\$K\$次，时间复杂度为\$KlogK\$，空间复杂度为\$KlogK\$，跑的似乎非常慢。。

#### Code： ####

#pragma GCC optimize(2, "inline", "Ofast") #include <bits/stdc++.h> using namespace std; const int N = 5e6 + 50; typedef long long ll; int n, k; ll a[N], s[N], nrt[N]; ll res; namespace PerTrie { int rt[N], cnt[N << 3], ch[N << 3][2]; int tot = 0; queue<int> rec; void Init() { for(int i = 1; i < (N << 3); i++) rec.push(i); } int Newnode() { int o = rec.front(); rec.pop(); cnt[o] = 0; ch[o][0] = ch[o][1] = 0; return o; } void Insert(int &o, int rt, ll x, int Bit) { if(!o || o == rt) o = Newnode(); cnt[o] = cnt[rt] + 1; ch[o][0] = ch[rt][0]; ch[o][1] = ch[rt][1]; if(Bit == -1) return ; int c = (1ll << Bit) & x ? 1 : 0; Insert(ch[o][c], ch[rt][c], x, Bit - 1); return ; } void Delete(int &o, int rt, ll x, int Bit) { if(!o || o == rt) o = Newnode(); cnt[o] = cnt[rt] - 1; ch[o][0] = ch[rt][0]; ch[o][1] = ch[rt][1]; if(Bit == -1) { if(cnt[o] == 0) rec.push(o), o = 0; return ; } int c = (1ll << Bit) & x ? 1 : 0; Delete(ch[o][c], ch[rt][c], x, Bit - 1); if(cnt[o] == 0) rec.push(o), o = 0; return ; } void Query(int o, ll x, int Bit) { if(Bit == -1) return ; int c = (1ll << Bit) & x ? 1 : 0; if(ch[o][c ^ 1]) Query(ch[o][c ^ 1], x, Bit - 1), res ^= (1ll << Bit); else Query(ch[o][c], x, Bit - 1); } } struct node { int R; ll val; bool operator < (const node &rhs) const { return val < rhs.val; }; }; priority_queue<node> Q; int main() { scanf("%d%d", &n, &k); PerTrie::Init(); for(int i = 1; i <= n; i++) scanf("%lld", &a[i]); for(int i = 1; i <= n; i++) s[i] = s[i - 1] ^ a[i]; PerTrie::Insert(PerTrie::rt[0], PerTrie::rt[n + 1], 0, 33); for(int i = 1; i <= n; i++) PerTrie::Insert(PerTrie::rt[i], PerTrie::rt[i - 1], s[i], 33), nrt[i] = i; for(int i = 1; i <= n; i++) { res = 0; PerTrie::Query(PerTrie::rt[i - 1], s[i], 33); Q.push( (node) { i, res }); } ll ans = 0; int tot = n + 1; while(k--) { node o = Q.top(); Q.pop(); ans += o.val; ll V = o.val ^ s[o.R]; PerTrie::Delete(PerTrie::rt[++tot], PerTrie::rt[nrt[o.R - 1]], V, 33); nrt[o.R - 1] = tot; if(PerTrie::rt[nrt[o.R - 1]] == 0) continue; res = 0; PerTrie::Query(PerTrie::rt[nrt[o.R - 1]], s[o.R], 33); Q.push( (node) { o.R, res } ); } printf("%lld\n", ans); return 0; }

2019.4.9 UPD：今天机房放出这道题目的加强版，数据范围如下:\$n \\leq 7.5 \* 10 ^ 5, k \\leq \\frac\{n \* (n + 1)\}\{2\}, a\_i < 2 ^ \{32\}\$，\$T L: 2s\$于是我们就有了一个\$O(nlogn)\$的优秀做法，暂时在\$loj\$ 和 \$luogu\$上\$rank1\$……马上就会放上来的……

2019.4.10 UPD：完了我被日爆了……果然我常数还是大啊……

这里继续讲一个复杂度为\$O(nlogn)\$的做法，并且需要的只是一棵\$Trie\$树。

首先我们还是做一遍前缀异或和，记这个数组为\$b\$。题目转化成点对异或前\$K\$大值之和。但是这是有序对，所以我们将\$K \* 2\$，即转化成了无序对，最后答案除以\$2\$即可。考虑到\$K\$非常的大，我们不能枚举\$K\$来得到答案，那么比较容易想到的就是枚举每一位计算贡献。在这之前，我们需要找出异或值第\$K\$大的数的值，之后要求的就是所有大于这个值的异或值之和。

考虑逐位确定第\$K\$大的每一位，假设我们这一位取的是\$1\$，那么对于某一个\$b\_i\$，假设当前所在节点为\$x\$，当前这一位的值为\$c\$，那么只有在\$ch\[x\]\[c\$ ^ \$1\]\$这个节点的子树中的\$b\_j\$才能够在该位产生贡献。我们记\$cnt\[x\]\$表示在\$Trie\$树上每个节点的子树中，有多少个实节点（即这个子树内包含多少个叶子节点）。那么对于当前这一位的答案，假设\$b\_i\$在\$Trie\$树上的当前位置是\$pos\_i\$，那么假设当前这一位上取\$1\$，则对于\$K\$的贡献就是\$s = \\sum\_i cnt\[ch\[pos\_i\]\[c\_i\$ ^ \$1\]\]\$（\$c\_i\$表示第\$i\$个前缀异或值这一位上是多少）。

类似树上二分，假设\$s \\leq k\$，说明这一位都取\$1\$是合法的，那么我们让答案\$K\$减去\$s\$，然后对于\$b\_i\$当前所在位置\$pos\_i\$，我们在$ch\[pos\_i\]\[c\_i $ ^ $ 1\]\$这个节点上打上\$b\_i\$这样一个标记，表示这个节点的子树中所有的\$b\_j$ ^ \$b\_i\$是会对答案产生贡献的，至于贡献我们最后一起算。然后\$pos\_i \\to ch\[pos\_i\]\[c\_i\]\$，即朝下一个地方走下去，并且我们记录\$ans\[i\]\$表示二进制下答案的这一位上会有多少个\$1\$，那么此时\$ans\[bit\] += s\$（\$bit\$表示当前在第几位）。  
如果\$s > k\$，说明这一位不能全部都取\$1\$，只能有\$k\$个取到\$1\$，那么此时答案\$ans\[bit\] += k\$，然后每个节点的\$pos\[i\] \\to ch\[pos\_i\]\[c\_i\$ ^ \$1\]\$，即往不会产生贡献的方向走。

这样我们在最后\$Dfs\$一遍\$Trie\$树，处理每个标记，把贡献加到答案里即可。但是由于我们处理的是类似于这样的\$b\_i\$ ^ \$b\_j + b\_i\$ ^ $b\_k + \\dots $ 这样的答案，所以我们处理每个标记的时候都需要拆位来计算。那么处理一个标记的时间就是\$O(log)\$的，总的复杂度就是\$O(nlog^2)\$的，仍然不够优秀。

继续考虑到在一个点上打的标记是怎样的形式，很容易发现，能够在某个相同的点上打的标记的这些数的集合\$\\\{ b\_i, b\_j, \\cdots, b\_m\\\}\$，一定是都在某一棵子树里的。于是我们的标记转化成了\$x\$与\$y\$这两棵子树中所有的\$b\_i\$两两异或的值之和作为贡献。考虑仍然是拆位做，这样我们需要知道某一棵子树中某一位上\$1\$的个数，有一种方法就是在插入\$Trie\$数之前，将\$b\$从小到大排序一遍，那么\$Trie\$树上的一个子树对应的就是数组中的一段区间，这样就非常好处理了。

复杂度之所以是\$O(nlog)\$的，在于这样\$(x,y)\$这样的标记个数不会超过\$O(n)\$对，因为标记只会在三度点上被打上，而\$Trie\$数上叶子节点个数为\$O(n)\$个，那么三度点的个数也是\$O(n)\$个，所以标记个数就是\$O(n)\$个。由于这个性质，我们还会发现一个节点\$x\$，只会至多和另一个节点\$y\$打上标记，这样就不用标记去重了。

至于如何打这个标记呢，由于我们需要\$b\_i\$在按照\$Trie\$树上正常走之后，第\$bit\$位时，在什么位置。于是我们记\$rpos\_i\$表示这个位置，那么每次\$rpos\_i\$都往\$ch\[rpos\_i\]\[c\_i\]\$这个方向走，打标记是，就相当于打上\$(ch\[rpos\_i\]\[c\_i\], ch\[pos\_i\]\[c\_i\$ ^ \$1\])\$这样的一对标记。我们将这样的标记存下来，最后一起算即可。注意这个时候\$K\$比较大，所以答案也会爆\$long long\$，记得开\_\_\$int128\$，并且别忘记除以2。

#### Code： ####

#pragma GCC optimize (3, "inline", "Ofast") #include <bits/stdc++.h> using namespace std; const int N = 7.5E5 + 50; const int M = 1.1E7 + 50; typedef long long ll; typedef pair<int, int> P; #define fi first #define se second #define mk make_pair typedef vector<int> Vec; typedef vector<P> VecP; int n, tot; ll k, s; ll a[N], b[N], ans[33]; int ch[M][2], l[M], r[M], dep[M], c[M]; int p1[N], p2[N], sum[N][33], gg[N], vis[M]; VecP t; void Insert(ll x, int idx) { int nw = 0; for(int i = 32; ~i; i--) { int son = (x >> i) & 1; if(!ch[nw][son]) ch[nw][son] = ++tot, dep[tot] = i, l[tot] = r[tot] = idx; nw = ch[nw][son]; l[nw] = min(l[nw], idx); r[nw] = max(r[nw], idx); c[nw] ++; } return ; } void print(__int128 x) { if(!x) return ; print(x / 10); putchar( (char)( x % 10 + '0') ); } void Solve() { for(int i = 0; i < (int)t.size(); i++) { int x = t[i].fi, y = t[i].se; for(int j = 0; j < dep[x]; j++) { int c1 = sum[r[x]][j] - sum[max(0, l[x] - 1)][j], c2 = sum[r[y]][j] - sum[max(0, l[y] - 1)][j]; ans[j] += (ll) c1 * (c[y] - c2) + (ll) c2 * (c[x] - c1); } } __int128 res = 0; for(int i = 0; i <= 32; i++) { if(!ans[i]) continue; res = res + (__int128) (ans[i] / 2) * (1ll << i); } if(res == 0) puts("0"); else print(res), puts(""); return ; } int main() { scanf("%d%lld", &n, &k); k = k * 2; for(int i = 1; i <= n; i++) scanf("%lld", &a[i]), b[i] = b[i - 1] ^ a[i]; sort(b, b + 1 + n); for(int i = 0; i <= n; i++) Insert(b[i], i); for(int i = 1; i <= n; i++) { for(int j = 0; j <= 32; j++) { sum[i][j] = sum[i - 1][j] + ((b[i] >> j) & 1); } } for(int i = 32; ~i; i--) { s = 0; for(int j = 0; j <= n; j++) { if(gg[j]) continue; int son = (b[j] >> i) & 1; s += c[ch[p1[j]][son ^ 1]]; p2[j] = ch[p2[j]][son]; } if(s <= k) { k -= s; ans[i] += s; for(int j = 0; j <= n; j++) { if(gg[j]) continue; int son = (b[j] >> i) & 1; if(ch[p1[j]][son ^ 1] && !vis[p2[j]]) { t.push_back( mk(p2[j], ch[p1[j]][son ^ 1])); vis[p2[j]] = ch[p1[j]][son ^ 1]; } p1[j] = ch[p1[j]][son]; if(!p1[j]) gg[j] = 1; } } else { ans[i] += k; for(int j = 0; j <= n; j++) { if(gg[j]) continue; int son = (b[j] >> i) & 1; p1[j] = ch[p1[j]][son ^ 1]; if(!p1[j]) gg[j] = 1; } } } Solve(); return 0; }

转载于:https://www.cnblogs.com/Apocrypha/p/10666886.html

[Link 1]: https://loj.ac/problem/3048
[Link 2]: https://darkbzoj.tk/problem/3689
[Link 3]: https://www.lydsy.com/JudgeOnline/problem.php?id=2006/problem/3048