【CF1305G】Kuroni and Antihype（Boruvka+高维前缀和）
题目链接
- 给定 \(n\) 个非负整数 \(a_{1\sim n}\)。
- 有一个初始为空的可重集合 \(S\)。每次选择一个尚未加入过 \(S\) 的元素 \(a_i\) 加入 \(S\)，且可以选择 \(S\) 中一个与 \(a_i\) 按位与为 \(0\) 的元素 \(a_j\) 获得 \(a_j\) 的收益。
- 求能获得的最大收益。
- \(1\le n\le2\times10^5\)，\(0\le a_i\le2\times10^5\)
最大生成树
首先可以新建一个权值为 \(0\) 的辅助点代表集合 \(S\)。则容易发现要求的其实就是最大内向树形图，其中一条边需要满足两端点权值按位与为 \(0\)，且其权值为指向点的权值。
最大树形图看起来比较麻烦，考虑到这里的边权比较特殊，尝试做一个转化。
如果把边权看作两端点权值之和减去指出点的权值，因为每个点会恰好作为一次指出点，这部分贡献可以提出来最后减掉，那么边权就可以记作 两端点权值之和。
这样一来无论哪个方向边权都是一样的，就可以当作一张无向图来做了。
然后便转化成了求最大生成树。
Boruvka+高维前缀和
这种问题应该非常容易就能想到 Boruvka 吧。
那么关键就在于如何求出与一个点按位与为 \(0\) 且颜色不同的最大点权。
\(x\) 与 \(y\) 按位与为 \(0\)，等价于 \(y\) 是 \(x\) 补集的子集。
所以考虑做一个高维前缀和，维护最大值以及与最大值颜色不同的一个次大值，就做完了。
代码：\(O(V\log V\log n)\)
#include
#define Tp template
#define Ts template
#define Rg register
#define RI Rg int
#define Cn const
#define CI Cn int&
#define I inline
#define W while
#define N 2000000
#define V 262144
#define LG 17
using namespace std;
namespace FastIO
{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
char oc,FI[FS],*FA=FI,*FB=FI;
Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
}using namespace FastIO;
int n,a[N+5];
struct S
{
int mx,mp,sx,sp;S(RI a=0,RI b=0,RI c=0,RI d=0):mx(a),mp(b),sx(c),sp(d){}//维护最大值次大值以及相应颜色
I S operator + (Cn S& o) Cn//合并
{
if(mx==o.mx) {if(mp^o.mp) return S(mx,mp,o.mx,o.mp);return sx>=o.sx?S(mx,mp,sx,sp):S(mx,mp,o.sx,o.sp);}
if(mx>o.mx) {RI x,y;o.mp^mp?(x=o.mx,y=o.mp):(x=o.sx,y=o.sp);return sx>=x?S(mx,mp,sx,sp):S(mx,mp,x,y);}
RI x,y;mp^o.mp?(x=mx,y=mp):(x=sx,y=sp);return o.sx>=x?S(o.mx,o.mp,o.sx,o.sp):S(o.mx,o.mp,x,y);
}
}s[V*10];
int f[N+5];I int fa(CI x) {return f[x]?f[x]=fa(f[x]):x;}
int ct,c[N+5],v[N+5],to[N+5],p[N+5];long long ans;void B()//Boruvka
{
RI i,j;for(i=0;i^V;++i) s[i]=S(-1,-1,-1,-1);for(i=1;i<=ct;++i) v[i]=p[i]=-1;//清空
for(i=1;i<=n;++i) s[a[i]]=s[a[i]]+S(a[i],c[i],-1,-1),f[i]=0;
for(j=0;j<=LG;++j) for(i=0;i^V;++i) i>>j&1&&(s[i]=s[i]+s[i^(1<