P11089 [ROI 2021] 手机游戏 (Day 1) 笔记

实则是模拟赛 #35 T4，但是模拟赛笔记已经太懒断更一个月了。

常见贪心：找到每个位置右边无法删掉的第一个位置 $R_i$，单调栈解决。

此时，每个位置都可以保留 $(i,R_i]$ 中的任意一个位置 $j$，并跳到 $j$ 处开始下一轮决策，假设最优位置是 $x$。

现在就变成了有以 $x$ 为开头的后缀的子串，和以 $j$ 为开头的后缀的子串，比较字典序，直接比较可以做到 $O(n^3)$，难以优化。

比较字典序有一种常见做法：处理出每个位置 $i$ 后面一段前缀 $[i,j]$ 的哈希，对于两个 $[i,n],[i^{\prime },n]$，类似直接比较，不断扩展 $j,j^{\prime }$ 直到哈希值不相同，比较 $s_j$ 与 $s_{j^{\prime }}$ 的字典序即可，这样做还是 $O(n^3)$ 的，但是哈希具有可合并的性质，且注意到从后往前做，$>i$ 开头的对应子串不会发生改变，因此使用倍增优化到 $O(n^2\log n)$。

这个比较并不用 $[i,R_i]$ 都做一次，只需要弹栈的时候做。

时间复杂度 $O(n\log n)$。