P4875 题解

显然这道题的解法与 \(8\) 强相关。从这一点下手，我们不难想到先对每一种奶牛做前缀和，这样我们可以做到 \(O(8)\) 查询每个区间是否可行，从而有了一个 \(O(4n^2)\) 的纯暴力做法。不知道多少 pts，反正不是正解。
下一步我们考虑优化。如果我们能快速地找到哪些区间是合法的，那么时间复杂度显然会大大降低。那么我们考虑对每个点编码，要同时把两个目的压缩在一个编码函数中，即每种奶牛出现的次数和出现的奶牛种类。我们不难写出下面的编码：

ull myEncode(int encoder, int i) {
    int first = 0;
    for (; first <= 7; first++)
        if (encoder & (1 << first)) {
            break;
        }
    ull ret = 0;
    for (int j = first + 1; j <= 7; j++)
        if (encoder & (1 << j))
            ret = (ret * 1001) + sum[i][j] - sum[i][first];
    return ret;
}

其中，\(encoder\) 状压的表示了哪些奶牛种类出现了，而 \(i\) 就是我们要编码的点。不难发现，如果两个点的前缀和之差（这里是八个颜色分别做差）相等，且选取的奶牛种类相等，那么编码值也相等。

接下来考虑每次加入一个端点怎么快速查询。先考虑从右端点，从右向左的加入端点，每次检查；同时考虑枚举所有出现奶牛的集合，并查编码值。这两种一个是 \(O(n^2)\) 的，一个是 \(O(2^8n)\) 的，都不优。我们把它们结合起来，可以从右向左依次加入某个颜色最后一个出现的位置，可以证明颜色出现的集合其变化不会超过八次。每次加入的时候强制选择这头奶牛，然后对此时的编码进行查询，若查询到就更新答案。
最后还有一个小问题：怎么修改。答案是直接暴力枚举端点然后暴力修改即可。时间复杂度可以接受。
代码是比较好写的，就不放了。核心的编码已经给出，如果你总是 WA，不妨考虑你的编码是否正确。