做题记录：数据结构 I

标 * 的题目是个人认为质量较高或比较符合个人喜好的题目。

*I. P5278 算术天才⑨与等差数列

尝试寻找一个序列满足为等差数列的充分必要条件。

• 显然需要有 \(\max - \min = (r - l)k\)。
• 直接要求等差的话，信息不好合并。但等差的限制有一个必要条件是，差分序列的 \(\gcd\) 为 \(k\)。较直觉的理解是，等差数列中任意两数的差都是 \(k\) 的倍数。
• 另外还需满足序列中的值两两不同即可。这个就很典了，记 \(a_i\) 的前驱位置为 \(\text{prev}_i\)，如果区间内 \(\text{prev}\) 的最大值小于左端点，则区间无相等数对。

关于条件二，这里给出一份严谨的证明：对于一个序列的任意排列，其差分序列的 \(\gcd\) 是相等的。

考虑任意一个排列都可以由邻项 swap 的操作产生，因此只需证明 \(\gcd(a_1 - a_2, a_2 - a_3, a_3 - a_4) = \gcd(a_1 - a_3, a_3 - a_2, a_2 - a_4)\)。

由 \(\gcd(a, b) = \gcd(a + b, b)\)，可知 \(\gcd(a_1 - a_2, a_2 - a_3) = \gcd(a_1 - a_3, a_2 - a_3)\)，对 \(a_3, a_4\) 同理。取二者的 \(\gcd\) 即可得证。\(\square\)

由此，只需维护区间的差分序列的 \(\gcd\)，区间 \(\max/\min\)，区间的 \(\text{prev}\) 的最大值即可。注意 \(k = 0\) 的情况。记录。

II. P3586 [POI2015] LOG

如果有 \(\sum \limits_{i = 1} ^ n \min(a_i, s) \geq s \times c\)，那么一定满足题设。

充分性可以理解为向 \(s\) 行 \(c\) 列的操作序列填数，则一定可以填满。必要性同理，小于 \(s \times c\) 显然填不满。记录。

*III. P8327 [COCI2021-2022#5] Radio

感觉这种拆贡献的 Trick 见过若干次了。

首先两个数不互质当且仅当其质因子集有交，因此就是在询问区间内有无两有交的集合。

考虑到质因子集的大小在 \(\omega\) 量级，可以直接把这个数拆成它的所有质因子放回到原序列中，最终问题等价于询问区间内是否存在相等的数。set + 线段树维护前驱即可。记录。

有一个类似的问题是，给定序列，区间询问 \(\text{lcm}\)。

先尝试对每个质因子独立讨论，此时就是在询问区间 \(\max\)。但是这样做复杂度不劣于 \(\mathcal{O}(\frac{qV}{\ln V})\)，没有前途。（也许一些差分技巧可解？）

如果序列中的数均为质数，这个问题显然容易转化：求区间内不同的数的乘积。

在这个思想的基础上，我们重新对每个质因子独立讨论。如果每个数都是 \(p_0^k\) 形式，那么可以想到这样一种转化：将每个数拆成 \(p_0^1, p_0^2, \dots, p_0^k\)，设每个数的贡献为 \(p_0\)，最终求区间不同的数的贡献积即可。本质上就是把 \(\max\) 的贡献拆开了。对于一般情况，对每个数的所有质因子都这样处理即可。

IV. P6617 查找 Search

显然可以想到维护 \(\text{prev}\)。

问题在于单点修改时有多个位置的 \(\text{prev}\) 发生改变，注意到我们本质上是将 \(R_i = [\text{prev}_i, i]\) 作为区间并询问是否存在 \(R_i \subseteq [L, R]\)，因此 \(R_i \subseteq R_j\) 时，\(R_j\) 可以被忽略。因此将 \(x\) 和 \(w - x\) 插入同一个 set，如果相邻项之和为 \(w\) 则更新后者的 \(\text{prev}\)。记录。

*V. P3747 [六省联考 2017] 相逢是问候

可以发现若干次操作后这个数是一个幂塔的形式：\(c^{c^{c^{a_i}}}\)。由扩展欧拉定理，只有 \(\Theta(\log p)\) 步是有用的。因此暴力作单点修改即可。

实现上的细节很多，一是要注意不要在操作前后数值相等时就认为数值已经收敛，事实上如果步数少到没有递归到 \(\varphi(p) = 1\)，则增加步数时还可能有变数。二是要注意正常写法是 \(\log^3\) 的，考虑到快速幂部分底数恒为 \(c\) 且模数很少，采用 BSGS 的思想预处理即可单次 \(\Theta(1)\)。总复杂度 \(\Theta(n \log^2 p)\)，记录。

VI. P3934 [Ynoi2016] 炸脖龙 I

此题就直白很多。同样是幂塔，直接迭代到 \(\varphi = 1\) 或 \(l = r\) 为止。区间加直接维护即可，求解时调用真实值进行计算。

但是数据范围很神秘，修改过程中会出现 long long 范围的数，留意快速幂部分的精度。总复杂度 \(\Theta(q \log n \log p)\)，记录。

*VII. CF896E Welcome home, Chtholly

第二分块。

众所周知第二个操作很难用普通数据结构维护，所以考虑按 \(\sqrt n\) 分块。

记当前块的最大值为 \(\text{Max}\)。第一个操作显然可以被暴力维护：每次将 \([x + 1, \text{Max}]\) 内的值减去 \(x\)。当每次的 \(x\) 都十分小时，这个做法显然具有错误的复杂度。但是换个角度想，若每次的 \(2x \geq \text{Max}\)，这个做法却具有了正确的复杂度，原因是每次操作会导致 \(\text{Max}\) 减少 \(\text{Max} - x\)，而单次操作的复杂度为 \(\Theta(\text{Max} - x)\)，因此单块总体复杂度是 \(\Theta(V)\) 的。

容易想到另一种暴力的维护方式，每次将 \([1, x]\) 内的值增加 \(x\)，然后全局打 \(-x\) tag。当每次的 \(x\) 都十分大时，这个做法的复杂度同样错误。类似地分析一下这个做法何时正确，可以发现当每次均有 \(2x \leq \text{Max}\) 时，这个做法同样可以做到单块时空 \(\Theta(V)\)。

那么这里就可以考虑平衡复杂度了，可以发现按 \(\frac{\text{Max}}{2}\) 为阈值，大于则选择方式一维护，否则选择方式二维护。同理可以证明单块总复杂度是 \(\Theta(V)\) 的。基本上类似于对值域区间作启发式合并。

现在我们从思想上基本完成了对本题的分析，下面考虑实现。一种直观的想法是，整块直接维护 \(\text{occ}\) 数组，根据上述分析暴力修改即可。但是处理散块时将遇到一个棘手的问题：如何还原元素的真实值。这里可以用最初分块的思想解决。如果要维护一个数组 \(g\)，\(g_x\) 表示值 \(x\) 在经过操作后的真实值，唯一的一个问题是，重构块时对之 init 的复杂度难免达到 \(\Theta(V)\)。最优秀的方法是，对每个值 \(x\) 维护其代表元 \(h_x\)（为方便，取 \(x\) 出现的第一个位置），并用并查集将具有相同值的位置合并，然后每次将 \(x\) 改为 \(y\) 时讨论一下即可。这样就避免了初始化值域过大的问题。

然后 \(\text{occ}\) 数组也不用记了，直接对 \(h_x\) 在并查集上的连通块求大小即可。

还有一个细节是在记录 \(\text{Max}\) 和 \(\text{Tag}\) 的基础上阈值究竟是多少。考虑实际的修改应该是将 \([x + \text{Tag} + 1, \text{Max}]\) 内的值减去 \(x\)，想象成对分裂后的两段区间作启发式合并，因此应用方式一的条件为 \(2(x + \text{Tag}) \geq \text{Max} + \text{Tag} \Rightarrow 2x \geq \text{Max} - \text{Tag}\)。

做题的时候出现了一些神奇的错误，顺便记录在这里。希望考场上能一遍写对。

• 当 \(h_x\) 和 \(h_y\) 同时存在且 \(h_x < h_y\) 时，\(h_y \gets h_x\) 的同时要作 \(a_{h_y} \gets y\)。
• 修改散块时，注意不要把应被减 \(x\) 的值在 build 时通过并查集被改成原来的值。
• \(\text{Max}\) 和 \(\text{Tag}\) 的值要精细维护。
• clear 有两种选择，一种是直接把原序列的所有值及所有修改中的 \(y\) 记录下来，另一种是直接清空当前序列中出现过的值，但要注意散块修改之前要先进行一次 clear。

总体复杂度 \(\Theta((q + V) \sqrt n)\)，大概带个 \(\alpha\) 因子。记录。

VIII. P4117 [Ynoi2018] 五彩斑斓的世界

完全同上，但由于空间限制较小，需要逐块处理。注意卡常，减少冗余操作。记录。

IX. P7447 [Ynoi2007] rgxsxrs

还有高手？

修改形式和第二分块完全一致，但值域非常大，显然不能套用第二分块。但这次询问的信息较为简单。