[CF1305G]Kuroni and Antihype

Description

$n$ 个点,每个点有点权 $a _i$,$i, j$ 之间有边当且仅当 $a _i \text{ AND } a _j = 0$。执行以下过程 $n$ 次:

  1. 选择一个点 $u$ 染色。
  2. 选择一个与 $u$ 相连的且已经染色的点 $v$,将 $a _v$ 计入答案。如果没有合法的 $v$,跳过该步。

输出最大的答案。

$$
1 \le n \le 2 \times 10 ^5, 0 \le a _i \le 2 \times 10 ^5
$$

Solution

设 $a _{n + 1} = 0$,并且默认 $n + 1$ 一开始已经被染色。

如果将每个点在 $2$ 过程中选择的点与它之间连一条边,会得到一棵树。如果将边权定义为 $a _i + a _j$,那么最终的答案即为边权之和减去点权之和,于是问题变为求解最大生成树。

$O(3 ^{18} \alpha (n))$

由于只有两个点与起来为 $0$ 才会有边,所以加法相当于是或。

那么考虑枚举边权 $w$,再枚举 $w$ 的子集 $x$,将 $x$ 与 $w \text{ XOR } x$ 全部用并查集连起来即可。

$O(18 \times 2 ^{18} \log n)$

考虑某个 B 开头求最大生成树的算法。初始时 $n + 1$ 个连通块,每次将每个连通块最大的出边找到然后并查集合并。可以证明不超过 $O(\log n)$ 次操作后图将连通。

如何找最大出边?因为子集有关的东西无法用数据结构方便的维护,也就是说不能到一个连通块之后将连通块里面的信息删除,特别麻烦。

一种特别巧妙的思路是用子集和 DP 求出 $S$ 的所有子集中点权的最大值,以及与这个最大值所在连通块不同的一个次大值。这样每个点的满足与其不在同一个连通块的最大出边只有可能在这两个中的一个。

每次利用子集和求出来的信息求出一个连通块的最大出边。

合并操作次数是 $O(n)$ 级别的所以并查集所带的 $\alpha (n)$ 不会计入总复杂度。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <cstring>
#include <iostream>

#define fir first
#define sec second

using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int N = 1 << 18;
const int maxN = 2e5 + 5;

int n;
LL ans;
int a[maxN];
int fa[maxN], size[maxN];
pii large[maxN];
pii best[N + 5][2];

int Find(int x)
{ return x == fa[x] ? x : fa[x] = Find(fa[x]); }

inline bool Merge(int u, int v)
{
int fu = Find(u), fv = Find(v);
if (fu == fv)
return false;
if (size[fu] > size[fv])
swap(fu, fv);
fa[fu] = fv, size[fv] += size[fu];
return true;
}

inline void Trans(pii A[2], pii B[2])
{
for (int i = 0; i < 2; ++i)
{
pii t = B[i];
if (t.fir > A[0].fir or (t.fir == A[0].fir and t.sec != A[0].sec))
{
if (A[0].sec != t.sec)
A[1] = A[0];
A[0] = t;
}
else if (t.fir > A[1].fir and t.sec != A[0].sec)
A[1] = t;
}
}

int main()
{
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n + 1; ++i)
fa[i] = i, size[i] = 1;
for (int i = 1; i <= n; ++i)
cin >> a[i], ans -= a[i];

int cnt = n + 1;
while (cnt > 1)
{
for (int i = 0; i < N; ++i)
best[i][0] = best[i][1] = pii(-1, -1);
for (int i = 1; i <= n + 1; ++i)
{
int id = Find(i);
if (best[a[i]][0].sec == -1)
best[a[i]][0] = pii(a[i], id);
else if (best[a[i]][1].sec == -1 and best[a[i]][0].sec != id)
best[a[i]][1] = pii(a[i], id);
}
for (int i = 0; i < 18; ++i)
for (int S = 0; S < N; ++S) if (S >> i & 1)
{
int T = S ^ 1 << i;
Trans(best[S], best[T]);
}
for (int i = 1; i <= n + 1; ++i)
large[i] = pii(-1, -1);
for (int i = 1; i <= n + 1; ++i)
{
int S = (N - 1) ^ a[i], id = Find(i);
if (best[S][0].fir == -1)
continue;
if ((best[S][0].fir ^ a[i]) > large[id].fir and best[S][0].sec != id)
large[id] = best[S][0], large[id].fir ^= a[i];
if ((best[S][1].fir ^ a[i]) > large[id].fir and best[S][1].sec != id)
large[id] = best[S][1], large[id].fir ^= a[i];
}
for (int i = 1; i <= n + 1; ++i) if (Find(i) == i and large[i].fir != -1 and Merge(large[i].sec, i))
--cnt, ans += large[i].fir;
}
cout << ans << endl;
return 0;
}