P14719 [RMI 2025] Cheap AI 题解

· · 题解

同学十月出的题（没公开），没想到出现在了十一月的 RMI 里。~严厉谴责 RMI。~

令 f(m) 表示 |t|=m 时最多能选出多少个 t。首先我们考虑当 m 给定时，f(m) 的值。我们可以考虑 DP，dp_i=dp_j+1，其中 j 表示上一个距离至少为 m 且接下来 m 个字符和当前位置起 m 个字符相同的位置。正确性显然。于是问题变成了对每一个 i 都找到对应的 j。

分别考虑 j 的两个限制：

首先我们考虑哈希，这样只需计算长度为 m 的子串的哈希就可以解决第一个限制。每次计算 dp_i 之前，再将 i-m 开始的长度为 m 的子串的哈希值加入哈希表中，就可以解决第二个限制。然而，哈希表的常数太大了，所以这么做是不行的，不过这启发我们使用后缀数组。

考虑后缀数组，第一个条件可以转化为 i 和 j 在 height 数组上，区间内所有的值都 \ge m，可以 O(n) 预处理出所有的值都 \ge m 的连续段，令 c_i 为 i 所在连续段的起始位置，我们发现可以直接用 c_i 代替刚刚的哈希值，然后用数组代替哈希表（因为 c_i\le n），同样可以满足第一个条件。这样做常数非常小。

如果直接对每一个 1\le m\le K 使用上述算法，时间复杂度为 O(nK)。但是，我们观察答案，会发现以下性质：对于所有 m，都有 f(m)\le\frac{n}{m}，因为取出的子串是不交的。同时，我们还知道，对于任意 i>j，都有 f(i)\le f(j)，这很容易证明。因此，我们考虑类似线段树的结构处理，对于一个区间，如果两端的答案相等，就代表中间的答案也和两端都一样，否则取中点将区间分为两个子区间递归即可。时间复杂度 O(n\sqrt n)，证明如下：

对于线段树任意一层，令深度为 d，则当前深度下每个区间的长度为 \frac{n}{2^d}，去掉前 c=2^{\frac{d}{2}} 个区间后剩下 m\ge\frac{n}{2^d}\times c=\frac{n}{2^{\frac{d}{2}}}，即 f(m)\le\frac{n}{m}\le2^{\frac{d}{2}} 的部分。由于在上一层一个长度为 \frac{n}{2^{d-1}} 的区间内部如果答案都相同则不会向下递归，因此这部分最多有 O(2^{\frac{d}{2}}) 个区间，总区间数量不超过 \sum_{d=1}^{\lceil\log_2 n\rceil}O(2^{\frac{d}{2}})=O(\sqrt n) 个。

参考文献：Determine A Non-Increasing Integer Sequence of Length n with a[k]<=n/k in O(sqrt(n)) Steps。