O(n log log V + m) 求前 m 小异或对

· · 算法·理论

其实是非常 naive 的东西,但是比较脑电波。不知道前人有没有想出来过,但我想出来之后觉得比较有意思,就发出来了。

如果只要求第 m 小异或对的话,前人应该是有 O(n \log V) 的做法的。但我可以顺便把前 m 小的全部求出来。

传统做法参见 P5283,用 01-trie + 堆做到 O((n+m)(\log n + \log V))。

不知道该怎么扩展到前 m 大异或对,如果有人想出来,欢迎告诉我。

给定一个长度为 n 的序列 a。我们对于所有满足 1 \le i < j \le n 的 (i,j),把 a_i \oplus a_j 放入一个可重集。求这个可重集中前 m 小的元素之和,对 2^{64} 取模的结果。

这个东西比较难做,所以我们先考虑如下判定性问题:

求这个可重集中,有多少个元素 <2^k(即在二进制中只有最低 k 位)。

判定性问题的做法是简单的。不难发现只要两个数除了最低 k 位都相同,这两个数就能贡献到答案。所以我们把所有数按 x>>k 分组,再计算答案即可。

这个判定性问题和原问题有什么关联呢?

考虑枚举 k=63\dots0。如果 <2^k 的元素数量 \ge m,那我们可以考虑用类似的方法,只求出答案序列中 <2^k 的元素,再截断排名 >m 的元素就好了。

那如果我们找到最小的 k,满足上述条件,那么 <2^k 的元素至多有多少个呢?观察到这样的元素至多有 2m+0.5n 个。证明稍微有点绕。

:::info[证明]{open} 感性理解一下,我们上文提到了要按 x>>k 分组,那么这样分出来的每个组,都是“按照 x>>(k-1) 分出来的组”中,每两个组合并成一个组,形成的。

一个大小为 x 的组,对答案的贡献为 f(x)=\frac{x(x-1)}2。

第 k 层的组由两个 k-1 层的子组合并,设两个子组的大小分别为 a,b。我们有 f(a+b)\le2(f(a)+f(b))+\min(a,b)。

对所有合并求和,得到:按照 x>>k 分出的组的贡献之和,小于等于两倍的“按照 x>>(k-1) 分出的组的贡献之和”,再加上 \sum\min(a,b)\le0.5n。

又因为 k 是满足贡献 \ge m 的最小的 k,所以 k-1 的贡献 <m,即 k 的贡献 <2m+0.5n。得证。

所以直接暴力求出所有的数就是对的,这样直接做的复杂度是 O(n \log V + m \log m),毕竟可能需要排序。把排序换成 nth_element,把枚举 k 换成二分,即可做到 O(n \log \log V+m)。

需要判掉 k=0 的 corner,不然会被卡成 O(n^2)。

:::success[代码 1] 使用了 umap,常数较大,但只要不对着 umap 卡,复杂度就是对的。

```cpp #include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; int n,m; ull s[5000005]; bool check(int k){ unordered_map<ull,int> umap; ull cur=0; for(int i=1;i<=n;++i) cur+=(umap[s[i]>>k]++); return (cur<(ull)m); } int cal(){ int l=-1,r=63; // l < ans, r >= ans while(r-l>1){ int mid=(l+r)>>1; if(check(mid)) l=mid; else r=mid; } return r; } vector<ull> solve(int k){ if(k==0) return vector<ull>(m,0); unordered_map<ull,vector<ull>> umap; vector<ull> res; for(int i=1;i<=n;++i){ for(ull p:umap[s[i]>>k]) res.push_back(s[i]^p); umap[s[i]>>k].push_back(s[i]); } nth_element(res.begin(),res.begin()+m-1,res.end()); res.erase(res.begin()+m,res.end()); return res; } ull ans=0; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n>>m; for(int i=1;i<=n;++i) cin>>s[i]; auto vec=solve(cal()); for(ull v:vec) ans+=v; cout<<ans<<endl; return 0; } ``` ::: :::success[代码 2] 如果允许对 $a$ 排序,那么可以利用 `x>>k` 的单调性省掉 umap。 时间复杂度 $O(n \log n + n \log \log V + m)$。 $n=5\times10^6$,$m=10^8$ 时,本地用时 2271 ms。 ```cpp #include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; int n,m; ull s[5000005]; bool check(int k){ ull cur=0;int cnt=0; for(int i=1;i<=n;++i){ if((s[i]>>k)==(s[i-1]>>k)) ++cnt; else cnt=1; cur+=cnt-1; } return (cur<(ull)m); } int cal(){ int l=-1,r=63; // l < ans, r >= ans while(r-l>1){ int mid=(l+r)>>1; if(check(mid)) l=mid; else r=mid; } return r; } vector<ull> solve(int k){ if(k==0) return vector<ull>(m,0); vector<ull> res;int cnt=0; for(int i=1;i<=n;++i){ if((s[i]>>k)==(s[i-1]>>k)) ++cnt; else cnt=1; for(int j=i-cnt+1;j<i;++j) res.push_back(s[i]^s[j]); } nth_element(res.begin(),res.begin()+m-1,res.end()); res.erase(res.begin()+m,res.end()); return res; } ull ans=0; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n>>m; for(int i=1;i<=n;++i) cin>>s[i]; sort(s+1,s+n+1); auto vec=solve(cal()); for(ull v:vec) ans+=v; cout<<ans<<endl; return 0; } ``` ::: 本文在写作完成后,使用了 deepseek 进行了测速和纠错。