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',n]\)，类似直接比较，不断扩展 \(j,j'\) 直到哈希值不相同，比较 \(s_j\) 与 \(s_{j'}\) 的字典序即可，这样做还是 \(O(n^3)\) 的，但是哈希具有可合并的性质，且注意到从后往前做，\(>i\) 开头的对应子串不会发生改变，因此使用倍增优化到 \(O(n^2 \log n)\)。

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

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