题目重述

我们有两个长度为 $n$ 的数组 $a$ 和 $b$，元素范围 $[0, m]$。

定义好对 (good pair) $(c, d)$：可以通过任意次以下操作将 $c$ 变成 $d$：

选 $i \neq j$，以及非负整数 $x < 2^{30}$，做：

$$c_i := c_i \& x,\quad c_j := c_j | x$$

我们允许两种移动：

1. 选 $i$，$a_i := a_i + 1$
2. 选 $i$，$b_i := b_i + 1$

可以超过 $m$。

问：最少移动次数，使 $(a,b)$ 成为好对。

---

第一步：好对等价条件

这个操作的特点是：

• 对 $c_i$ 做 AND 只能清除某些 1 位
• 对 $c_j$ 做 OR 只能设置某些 1 位
• 两个操作同时发生，且 $x$ 任意

经过推导（见题解或结论），好对等价于：

1. $c = d$
   显然成立（不需要操作）

   或者

2. 存在 $i \neq j$ 使得 $d_i$ 是 $d_j$ 的子掩码
   即 $d_i \& d_j = d_i$（$d_i$ 的所有 1 位在 $d_j$ 中也是 1）

为什么？
如果 $d$ 中有这样的子掩码对，那么可以选 $x = d_j$ 等，反复操作让 $c$ 变成 $d$。反之，如果没有这样的对，则 $c$ 无法变到 $d$（证明略）。

---

第二步：最少移动次数分解

我们只能增加元素，所以最终数组元素 $\ge$ 原始值。

情况 1：最终 $a = b$

移动次数：

$$\text{cost}_1 = \sum_{i=1}^n |a_i - b_i|$$

因为如果 $a_i < b_i$，需要增加 $a_i$ 共 $b_i - a_i$ 次；
如果 $b_i < a_i$，需要增加 $b_i$ 共 $a_i - b_i$ 次。

---

情况 2：最终 $b$ 中存在子掩码对

我们只需要考虑修改 $b$（因为一旦 $b$ 满足条件，$a$ 可以通过操作任意匹配 $b$，无需额外移动）。

目标：选两个不同下标 $p, q$，增加 $b_p, b_q$ 到 $b'_p, b'_q$，使得 $b'_p$ 是 $b'_q$ 的子掩码，且增加值之和最小。

即：

$$\text{cost}_2 = \min_{i \neq j} \min_{\substack{b'_i \ge b_i \\ b'_j \ge b_j \\ b'_i \& b'_j = b'_i}} \big( (b'_i - b_i) + (b'_j - b_j) \big) $$

---

第三步：图论模型

构造图 $G$，顶点为 $0$ 到 $2m$（可能超过 $m$ 但不超过 $2m$）。

边：

• $u \to u+1$，权重 $1$（模拟 $+1$ 操作）
• $u \to v$，如果 $v$ 是 $u$ 的子掩码，权重 $0$（因为可以一步操作实现）

那么，从 $b_i$ 到 $b_j$ 的最短路径长度 $L$ 表示：
将 $b_i$ 增加到某个值，再跳到 $b_j$ 的子掩码（或反过来），最小增加值之和。

注意：我们需要的是两个不同源点之间的最短路径。

---

第四步：多源 0-1 BFS / DP 实现

我们维护每个顶点 $u$ 的两个最近源点（及其距离）：

• dist1[u], id1[u]：最近源的距离和编号
• dist2[u], id2[u]：次近源的距离和编号

初始化：
每个 $b_i$ 作为源，dist1[b_i] = 0，id1[b_i] = i。
如果 $b_i$ 重复出现，则 dist2 立即为 0。

传播分三阶段（保证所有最短路径被找到）：

1. 向上传播（$+1$ 边）
   从小到大遍历 $u$，用 $u$ 更新 $u+1$：

   • 如果 dist1[u]+1 < dist1[u+1]，则替换
   • 否则如果 dist1[u]+1 < dist2[u+1] 且 id1[u] != id1[u+1]，则更新次近

2. 子掩码传播（$0$ 边）
   从大到小遍历 $u$，枚举 $u$ 的所有子掩码 $v$：

   • 用 dist1[u] 更新 $v$
   • 注意不同源

3. 向下传播（$-1$ 边）
   从大到小遍历 $u$，用 $u$ 更新 $u-1$（因为可以反向走 $-1$ 来模拟 $+1$ 到别的值）

每次更新时，如果 id1[u] != id1[v]，则更新 dist2。

最终答案：

$$\text{cost}_2 = \min_{u} \big( \text{dist1}[u] + \text{dist2}[u] \big) $$

---

第五步：时间复杂度

• 顶点数 $O(m)$
• 枚举子掩码总复杂度 $O(m \log m)$（每个数的子集个数平均 $O(\log m)$）
• 传播 $O(m)$
• 总复杂度 $O(m \log m + n)$，可过 $2\times 10^6$

---

第六步：最终答案

$$\text{ans} = \min(\text{cost}_1, \text{cost}_2)$$

---

第七步：代码实现要点

• 注意 $m$ 可达 $2\times 10^6$，数组开 $2m+5$ 足够
• 枚举子集：sub = (sub-1) & u
• 用 INF 表示无穷大
• 重复值直接输出 $0$（因为 $b$ 已满足条件）

---

结论

本题的核心是：

1. 发现好对等价于数组相等或 $b$ 中有子掩码对
2. 将问题转化为图上多源最短路径问题
3. 用 DP 维护最近和次近源
4. 通过三阶段传播保证找到所有可能的最小增加值