根号分治简单复习题

【SHOI2006】作业 Homework

给定一个集合为 \(S\)，初始为空，你需要执行以下两个操作共 \(N\) 次。

操作一，在集合 \(S\) 中加入一个新元素，其代号为 \(X\)，保证 \(X\) 在当前集合中不存在。

操作二，在当前的集合 \(S\) 中询问所有元素 \(\bmod\ Y\) 最小的值。

\(N,X,Y\le 3\times 10^5\)

根据 \(Y\) 的大小，可以设计出两种做法：

• 第一种，枚举 \(i\times Y \le v\)，显然答案为 \(\min _{i\in[1,\frac{n}{y}]\cap \Z} \{v-i\times Y\}\)，这是容易处理的，单次复杂度 \(\mathcal O(\dfrac{V}{Y})\)。
• 第二种，处理出 \(1 \sim B\) 的 \(\min\)，每次加入新元素时修改一下，复杂度为 \(\mathcal O(B)\)。

平衡一下查询加修改复杂度为：\(\mathcal O(\sqrt V)\)，如果用 set 实现为 \(\mathcal O(\sqrt {V\log n})\)。

Magic Triples (Hard Version) *800

给定一个序列 \(a\)，统计满足下面条件的三元组数量。

• \(1 \le i, j, k \le n\)。
• \(i\)、\(j\)、\(k\) 两两不同。
• 存在一个正整数 \(b\)，使得 \(a_i \cdot b = a_j\) 且 \(a_j \cdot b = a_k\)。

\(n \le 2\cdot 10^5, 1 \le a_i \le 10^9\)。

暴力的想法是：枚举 \(b\)，显然其不超过 \(\sqrt V\)，再枚举 \(b\) 的一个倍数 \(a_j\)，map 统计 \(a_j/b\) 和 \(a_j\cdot b\) 的个数即可，\(\mathcal O(n\sqrt V)\) 可以通过 Easy Version。

此处容易发现，对于 \(b\) 超过某个阈值 \(B\) 之后，可以转为枚举 \(a_j \le V/B\)，然后枚举 \(a_j\) 的因数个数，复杂度 \(O(n\sqrt{V/B})\)。

• 对于小于等于 \(B\) 的 \(b\)，枚举 \(b \mid a_j\)，\(O(nB)\) 即可完成。
• 对于大于 \(B\) 的 \(b\)，枚举 \(a_j\)，再枚举因数 \(b\)，\(O(n\sqrt {V/B})\) 即可完成。

平衡：\(O(nB)+O(n\sqrt{V/B})\ge O(n\sqrt[3]V)\)，应该可以通过。