O(n log log V + m) 求前 m 小异或对
_buzhidao_
·
·
算法·理论
其实是非常 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 进行了测速和纠错。