考虑枚举最大的字母所处的位置 \(i\) 作为端点和最小的字母 \(j\)。
然后就有记录一下前缀出现次数 \(cnt\),枚举一个区间。
\[cnt_{i, ch_i} - cnt_{i, j} - (cnt_{i',ch_i} -cnt_{i', j}) \]求这个式子最大值。显然这两个式子相似,记录一下关于 \(ch_i\) 的 \(cnt\) 前缀最小值即可。
大概是 \(O(26n)\) 的。
代码自己去贺题解区的,写的都比我好。
标签:cnt,ch,POI2011,ROZ,P3519,Difference From: https://www.cnblogs.com/Custlo/p/17520808.html