主要思路
刚开始看到分治的标签就下定决心用分治做，没一会发现信息非常难利用就弃疗了。考虑用类似于 KMP 的 AC 自动机的方法完成本题。
首先设置\(dp[i]\)为以\(i\)开头向右延伸的答案，那么我们往左的时候可以合并之，并设置\(nxt[i]\)来进行跳跃；由于得到\(nxt\)数组的过程暴力做时间复杂度会 GG，所以我们可以使用类似 AC 自动机的方式用 Map 合并信息：交换\(nxt[i]+1\)位置的 Map 并设置当前位置。最后做 DP 即可。
刚开始看到分治的标签就下定决心用分治做，没一会发现信息非常难利用就弃疗了。考虑用类似于 KMP 的 AC 自动机的方法完成本题。
首先设置\(dp[i]\)为以\(i\)开头向右延伸的答案，那么我们往左的时候可以合并之，并设置\(nxt[i]\)来进行跳跃；由于得到\(nxt\)数组的过程暴力做时间复杂度会 GG，所以我们可以使用类似 AC 自动机的方式用 Map 合并信息：交换\(nxt[i]+1\)位置的 Map 并设置当前位置。最后做 DP 即可。
假的单调队列哦。
考虑将每个类别元素的下标记好，然后先把每个类别标号最小的放入 multiset，然后对答案进行更新：每次取出最大和最小值做差更新，然后把最小值的下标更新后重新扔进 multiset 中。如果 multiset 中所有的类别都已经枚举完毕，那么直接跳出循环进行输出即可。