2019 牛客暑期多校训练营 #1 后记

喵 ε(*´･ω･)з 本帖的内容是 {赛后讨论的} \ {赛前知道的} \cap {有趣的} 想法。目前会包含 3 个题目，分别是：

C 的贪心 (Thanks to quailty)
D 的漂亮解释 (Thanks to nobody)
G 的 O(n \sqrt{n} + n \log^2 n) (Thanks to 300iq)

Euclidean Distance

在 CCPC 2019 女生赛中，C 题（？我不确定）如下：给出 n 个数 $a_1, a_2, \dots, a_n$ 和整数 m，求 n 个非负整数 $x_1, x_2, \dots, x_n$ 使得 $x_1 + x_2 + \dots + x_n = m$ 且 $\sum_{i = 1}^n f_i(x_i)^2$ 最小，其中 $f_i(x) = (x - a_i)^2$ . 做法是贪心，从 $x_1 = x_2 = \dots = x_n = 0$ 开始，每次选择 $h_i(x_i) = f_i(x_i + 1) - f_i(x_i) = 2(x_i - a_i) + 1$ 最小的 i， $x_i \leftarrow x_i + 1$ . 因为 $h_i(x)$ 关于 x 单调递增，所以也可以等效地，二分 $\lambda$ ，把 $x_i$ 设成 $y_i = \max\{\frac{\lambda - 1}{2} + a_i, 0\}$ . 我们只需找一个 $\lambda$ 使得 $\sum_{i = 1}^n y_i = m$ 即可。
实际上，本题可以看作是上题的连续版本，我们只需把差分 $f_i(x_i + 1) - f_i(x_i)$ 换成微分 $h_i(x) = \frac{\mathrm{d}}{\mathrm{d} x} f_i(x) = 2(x - a_i)$ ，继续推导可以得到原解的公式。
另外，连续版本曾经作为 World Finals 2014 B 题的子问题出现（赛场上 WA 了若干次 QAQ）。

Substring 2

我们用 $\mathrm{enc}(u)$ 来表示串 u. $\mathrm{enc}(u)_i$ 是最小的 j > 0 满足 $u_i = u_{i - j}$ . 即 $\mathrm{enc}(u)_i$ 是 i 与上一个等于 $u_i$ 的字符的距离。容易验证， $\mathrm{enc}(u) = \mathrm{enc}(v)$ 等价于 u, v 同构。

我们维护一个持久化数组（线段树） $\mathrm{aux}$ . 从后往前考虑字符 $u_i$ , 每次找到最小的 j > 0 满足 $u_i = u_{i + j}$ , 把 $\mathrm{aux}[i + j]$ 修改为 j. 那么对于后缀 s[i:]，假设考虑 $u_i$ 后的数组版本是 $\mathrm{aux}_i$ , 那么 $\mathrm{enc}(s[i:]) = \mathrm{aux}_i[i:]$ . 因为 $\mathrm{enc}(s[i:])$ 对应于可持久化线段树某个版本的某个区间，如果在线段树上维护节点的 Rabin Karp Hash 值，我们可以 $O(\log n)$ 得到 $\mathrm{enc}(s[i:])$ 某个前缀的 RK Hash. 如果我们二分 \texttt{LCP}, 可以在 $O(\log^2 n)$ 比较两个串的字典序。
实际上，我们可以用持久化分块数组代替持久化线段树，那么查询区间 Hash 值降为 O(1), 总复杂度降为 $O(n \sqrt{n} + n \log^2 n)$ .