喵 ε(*´･ω･)з 本帖的内容是 {赛后讨论的} \ {赛前知道的} \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 个数 和整数 m，求 n 个非负整数 使得 且 最小，其中 . 做法是贪心，从 开始，每次选择 最小的 i，. 因为 关于 x 单调递增，所以也可以等效地，二分 ，把 设成 . 我们只需找一个 使得 即可。
实际上，本题可以看作是上题的连续版本，我们只需把差分 换成微分 ，继续推导可以得到原解的公式。
另外，连续版本曾经作为 World Finals 2014 B 题的子问题出现（赛场上 WA 了若干次 QAQ）。

Substring 2

我们用 来表示串 u. 是最小的 j > 0 满足 . 即 是 i 与上一个等于 的字符的距离。容易验证， 等价于 u, v 同构。

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