题目分析

问题本质

我们有一个由 n+m 个集合组成的序列，前 n 个集合具有特殊结构：Aᵢ 是 i 的倍数的集合。后续 m 个集合通过并集、交集、补集运算从前面的集合生成。需要回答 q 个询问，每个询问给定集合编号 x 和数字 v，判断 v 是否属于 Aₓ。

数据范围分析

• n ≤ 50000
• m ≤ 400000
• q ≤ 1000000

直接存储每个集合（如用 bitset）需要大约 450000 × 50000 / 8 ≈ 2.8 GB，内存不可行。

关键观察

1. 初始集合的结构：v ∈ Aᵢ 当且仅当 i 整除 v。这意味着对于固定的 v，其所属的初始集合由 v 的约数决定。
2. 运算的布尔性质：每个集合 Aₓ 可以看作一个布尔函数 fₓ(v)。初始时 fᵢ(v)=1 当且仅当 i∣v。运算对应布尔操作：
   • 并集：f = fₐ ∨ fᵦ
   • 交集：f = fₐ ∧ fᵦ
   • 补集：f = ¬fₐ

难点与挑战

• 如果对每个询问单独计算，需要遍历运算图，最坏 O(m) 时间，总 O(qm) 不可接受。
• 如果对每个数字 v 单独计算所有集合的归属，需要 O(nm) 时间，同样不可接受。
• 内存限制使得无法存储所有集合的完整表示。

核心思路：分批处理与位运算并行

利用位运算同时处理多个数字的归属状态：

1. 将数字 1..n 分成若干批，每批 B 个数字（例如 B=64，对应一个 unsigned long long 的位数）。
2. 对每一批，为每个集合计算一个 B 位的位向量，表示该批中哪些数字属于这个集合。
3. 按顺序计算所有集合在该批上的位向量：初始集合通过约数关系设置，后续集合通过位运算（按位或、按位与、按位取反）计算。
4. 对于该批内的数字 v，回答所有相关询问。

算法步骤

1. 预处理：
   • 计算每个数字 v 的所有约数（用于初始化）。
   • 将询问按 v 分组，便于批处理时快速查找。
2. 分批处理：
   • 对于每批（例如每 64 个数字）： a. 初始化数组 val[]，val[i] 表示集合 Aᵢ 在该批上的位向量。 b. 对于批内的每个数字 v，枚举其所有约数 i，将 val[i] 的对应位设为 1。 c. 按编号顺序计算后续集合的位向量：
     • 并集：按位或
     • 交集：按位与
     • 补集：按位取反后与掩码（掩码确保只保留有效位） d. 处理该批内所有询问：检查对应集合位向量的相应位。
3. 输出：按询问顺序输出答案。

复杂度分析

• 时间：
  • 预处理约数：O(n log n) ≈ 5×10⁴ × 10 = 5×10⁵
  • 分批处理：设批次数 K = ⌈n/64⌉ ≈ 781
    • 每批初始化：遍历批内数字的约数，总操作次数等于所有数字的约数个数之和，约 5×10⁵
    • 每批计算 m 个运算：每次运算是 O(1) 的位运算，总位运算次数约 K×m ≈ 3.12×10⁸
    • 每批回答询问：总共 q 次回答，每次 O(1)
  • 总操作量约 3.2×10⁸ 次位运算，现代 CPU 可在合理时间内完成。
• 空间：
  • 存储约数列表：O(n log n) ≈ 5×10⁵ 个整数
  • 存储询问分组：O(q)
  • 每批的位向量数组：O(n+m) ≈ 4.5×10⁵ 个 64 位整数，约 3.6 MB
  • 总内存使用约几百 MB，符合限制。

优化细节

• 使用 unsigned long long 进行位运算，编译器能生成高效指令。
• 补集运算需要掩码，以正确处理不满 64 位的批次。
• 只清零每批需要的部分数组（前 n 个集合），减少内存写入。
• 使用 scanf/printf 处理大量输入输出。

总结

该问题通过以下技巧高效解决：

1. 利用初始集合的整除性质，将集合成员关系转化为约数关系。
2. 位运算并行，同时处理一批数字的归属判断。
3. 分批处理，将总计算量控制在可接受范围，同时保持内存使用合理。

这种方法平衡了时间与空间，能够在给定限制内处理最大规模的数据。