题解：P14567 【MX-S12-T2】区间

· · 题解

由于 f 单调不降，若一个合法区间包含另一个合法区间，那么这个大的区间一定不优。

如何判断区间合法？我们可以使用随机化哈希，对颜色分组，使每一种颜色的异或和为 0。然后做一遍前缀和，找前缀和相等的端点即可。

由于没有区间包含，这样的合法区间个数是 O(n) 的。

接下来我们充分发挥人类智慧，根据直觉，区间长度小的一定不劣，这样我们按照区间长度排序，取前 1000 个区间暴力求值。这样子跑得飞快，最慢的点在 705ms 内就能跑出。