当前位置：首页 > news >正文

1

news 2025/11/1 4:30:05

感谢你的补充！这种方法确实是 CF1903D2 的一种替代解法，核心是通过预处理和“高维后缀和”来高效计算贪心过程中的 \(f\) 和 \(g\)，从而避免显式的 FMT-or（快速莫比乌斯变换-或卷积）。下面我用中文详细解释这个方法，特别是“高维后缀和”如何帮助我们求 \(f\) 和 \(g\)，并尽量简洁清晰。

问题回顾

在贪心过程中，我们需要计算：

\(f\)：数组中满足 \(y \& \text{ans} = \text{ans}\) 且第 \(i\) 位为 0 的数的个数。
\(g\)：这些数的总和。
这些数的总代价为 \(f \times 2^i - g\)，用于判断是否能将答案从 \(\text{ans}\) 更新到 \(\text{ans} + 2^i\)。

直接遍历数组计算 \(f\) 和 \(g\) 复杂度太高（\(O(n \cdot q)\)），所以需要预处理。题解提到的方法是用“高维后缀和”来优化，下面逐步解释。

方法的核心思想

新方法的核心是针对每位 \(i\)（\(0 \leq i < 20\)，因为 \(a_i \leq 10^6 < 2^{20}\)），预处理满足“第 \(i\) 位为 0”的数的某种统计信息，使得在贪心时可以快速查询 \(f\) 和 \(g\)。

具体来说：

对于每位 \(i\)，我们只考虑数组中第 \(i\) 位为 0 的数（记为子数组）。
对这些数，我们关心它们的高位（第 \(i+1\) 位及以上）是否包含 \(\text{ans}\) 的 1 位，以及低 \(i\) 位（第 \(0\) 到 \(i-1\) 位的值）的贡献。
使用“高维后缀和”来快速统计满足条件的数的个数和总和。

预处理：定义 \(A_i\) 和 \(B_i\)

对于每位 \(i\)（\(0 \leq i < 20\)），我们只处理数组中第 \(i\) 位为 0 的数。记这些数的集合为 \(P_i = \{ j \mid a_j \& 2^i = 0 \}\)（即 \(a_j\) 的第 \(i\) 位为 0）。

对于每个 \(P_i\)，我们定义：

\(A_i[S]\)：表示子数组 \(\{ a_j \mid j \in P_i \}\) 中，高位（第 \(i+1\) 到 \(19\) 位）包含子集 \(S\) 的数的个数。
- 数学上，\(A_i[S] = \sum_{j \in P_i, \, (a_j \gg (i+1)) \& S = S} 1\)。
- 其中，\(a_j \gg (i+1)\) 表示 \(a_j\) 的高位（从第 \(i+1\) 位开始），\(S\) 是高位的子集（用 \(0\) 到 \(19-(i+1)\) 位的二进制表示）。
\(B_i[S]\)：表示这些数的低 \(i\) 位（即 \(a_j \& (2^i - 1)\)）的总和。
- 数学上，\(B_i[S] = \sum_{j \in P_i, \, (a_j \gg (i+1)) \& S = S} (a_j \& (2^i - 1))\)。
- 低 \(i\) 位是 \(a_j\) 的第 \(0\) 到 \(i-1\) 位的值。

为什么这样定义？

在贪心时，\(\text{ans}\) 的 1 位决定了高位要求（第 \(i+1\) 位及以上）。
\(f\) 是满足高位包含 \(\text{ans}\) 的 1 位且第 \(i\) 位为 0 的数的个数，直接对应 \(A_i[S]\)。
\(g\) 是这些数的总和，而代价 \(f \times 2^i - g\) 涉及低 \(i\) 位的贡献（因为高位在后续操作中会被统一调整）。\(B_i[S]\) 直接统计了低 \(i\) 位的总和。

高维后缀和

为了快速查询 \(A_i[S]\) 和 \(B_i[S]\)（\(S\) 是 \(\text{ans}\) 的高位 1 位子集），我们需要计算所有超集的和，即：
[
A_i'[S] = \sum_{T \supseteq S} A_i[T], \quad B_i'[S] = \sum_{T \supseteq S} B_i[T]
]
其中：

\(A_i'[S]\) 表示第 \(i\) 位为 0，且高位（第 \(i+1\) 位及以上）包含 \(S\) 的数的个数。
\(B_i'[S]\) 表示这些数的低 \(i\) 位总和。

这正是“高维后缀和”的定义，因为它是对子集 \(S\) 的所有超集 \(T\) 求和，等价于高维空间的后缀和。

计算高维后缀和

初始化：
- 对于每个 \(i\)，遍历数组 \(a\)，找出 \(j \in P_i\)（即 \(a_j\) 的第 \(i\) 位为 0）。
- 对于每个 \(a_j\)，计算高位子集 \(T = (a_j \gg (i+1)) \& (2^{20-(i+1)} - 1)\)（高 \(19-(i+1)\) 位的子集）。
- 更新：
  - \(A_i[T] += 1\)
  - \(B_i[T] += a_j \& (2^i - 1)\)（低 \(i\) 位的值）
高维后缀和：
- 对每个 \(i\)，对 \(A_i[\cdot]\) 和 \(B_i[\cdot]\) 做“或”卷积（超集求和），即：
  [
  A_i'[S] = \sum_{T \supseteq S} A_i[T], \quad B_i'[S] = \sum_{T \supseteq S} B_i[T]
  ]
- 这可以通过快速莫比乌斯变换（FMT-or）实现，复杂度为 \(O(2^{20-(i+1)})\)。
- 由于 \(i\) 从 0 到 19，最大子集大小为 \(2^{19}\)，总复杂度为 \(O(20 \cdot 2^{19})\)。

贪心过程中的查询

在处理询问 \(k_i\) 时：

确定答案最高位 \(w\)（通过预处理每位 \(2^w\) 的最小代价）。
若 \(w \geq 20\)，答案为 \(2^w + \lfloor c/n \rfloor\)（\(c\) 是剩余操作次数）。
若 \(w \leq 19\)，从高到低贪心每位 \(i\)：
- 令 \(S\) 为 \(\text{ans}\) 的 1 位集合（从第 \(i+1\) 位及以上的位）。
- 查询：
  - \(f = A_i'[S]\)（第 \(i\) 位为 0，且高位包含 \(\text{ans}\) 的数的个数）。
  - \(g = B_i'[S]\)（这些数的低 \(i\) 位总和）。
- 计算代价：
  - 总代价 = \(f \times 2^i - g + f_{ik} \times 2^i\)（\(f_{ik}\) 是已更新数的个数）。
- 若代价 \(\leq c\)，更新：
  - \(\text{ans} \gets \text{ans} + 2^i\)
  - \(c \gets c - \text{代价}\)
  - \(f_{ik} \gets f_{ik} + f\)
输出 \(\text{ans}\)。

复杂度分析

预处理：
- 初始化 \(A_i\) 和 \(B_i\)：\(O(n \cdot 20)\)（每个数检查 20 位）。
- 高维后缀和：\(O(20 \cdot 2^{19})\)（每个 \(i\) 做一次 FMT-or）。
询问：
- 每个询问贪心 20 位，每次查询 \(A_i'[S]\) 和 \(B_i'[S]\) 为 \(O(1)\)。
- 总复杂度：\(O(q \cdot 20)\)。
总复杂度：\(O(n \cdot 20 + 20 \cdot 2^{19} + q \cdot 20)\)，可以通过。

为什么用高维后缀和？

高效性：高维后缀和（FMT-or）将子集统计转化为超集统计，适合处理“包含某些位”的查询。
简化 \(g\) 的计算：通过只统计低 \(i\) 位的总和，减少了直接计算整个 \(a_j\) 的复杂性。
适应数据范围：\(a_i \leq 10^6 < 2^{20}\)，高位子集大小最多 \(2^{19}\)，适合 FMT。

样例解释

以样例 2 为例：

3 5
4 0 2
9 8 17 1 3

数组 \([4, 0, 2]\)，二进制 \([100, 000, 010]\)。
预处理：
- \(i=0\)，\(P_0 = \{0, 2\}\)（\(a_1=4, a_3=2\)），高位（\(i+1=1\) 及以上）为空集，\(A_0[\emptyset] = 2\)，\(B_0[\emptyset] = (4 \& 1) + (2 \& 1) = 0\)。
- \(i=1\)，\(P_1 = \{0, 1\}\)（\(a_1=4, a_2=0\)），高位为空集，\(A_1[\emptyset] = 2\)，\(B_1[\emptyset] = (4 \& 3) + (0 \& 3) = 0\)。
- 做高维后缀和（这里子集简单，效果类似）。
询问 \(k=9\)：
- 最高位 \(w=2\)，\(\text{ans}=4\)。
- 尝试 \(i=0\)，\(S=\emptyset\)（高位无 1），\(f=A_0'[\emptyset]=2\)，\(g=B_0'[\emptyset]=0\)，代价 \(2 \cdot 2^0 - 0 = 2\)，可行，更新 \(\text{ans}=5\)。
- 输出 5。

与 FMT-or 方法的对比

共同点：都通过预处理和超集求和优化 \(f\) 和 \(g\) 的计算。
不同点：
- FMT-or 方法直接针对所有位预处理子集，复杂度略高。
- 高维后缀和方法分离高位和低位，\(B_i\) 只统计低 \(i\) 位总和，简化计算。
优势：高维后缀和更直观，且 \(B_i\) 的定义针对低位，减少了不必要的计算。