考虑枚举最大的字母所处的位置 \(i\) 作为端点和最小的字母 \(j\)。
然后就有记录一下前缀出现次数 \(cnt\)，枚举一个区间。
\[cnt_{i, ch_i} - cnt_{i, j} - (cnt_{i',ch_i} -cnt_{i', j})
\]
求这个式子最大值。显然这两个式子相似，记录一下关于 \(ch_i\) 的 \(cnt\) 前缀最小值即可。
大概是 \(O(26n)\) 的。
代码自己去贺题解区的，写的都比我好。
P3519 [POI2011]ROZ-Difference
发布时间 2023-07-02 15:00:22作者: Custlo