题解：P9842 [ICPC 2021 Nanjing R] Klee in Solitary Confinement

WZwangchongming · 2025-06-15 21:08:24 · 题解

可莉可爱捏！但是没有芙芙可爱！

Solution：

直接考虑枚举众数的值。

假设枚举的这个众数的值为 x。那么我们可以知道，如果操作了一个区间 [l,r]，且这个区间里有 a 个 x 和 b 个 x-k，那么最后 x 的个数就会增加 b-a 个。

所以就有一个很自然的贪心：让 x 产生的贡献为 -1，x-k 的贡献为 1，其余的贡献为 0，再求一个最大子段和。那么 x 的最多出现次数只需要再加上 x 原来的出现次数。最后对所有 x 取一个最大值就可以得到答案。

但是这个贪心的时间复杂度是 O(n^2) 的。

明显，既不是 x 又不是 x-k 的那些位置对答案不会产生影响。因此，对于每一个 x，单独把所有值为 x 或 x-k 的位置存进一个 vector 里，在每个 vector 中做最大子段和。这样每个数最多被放进 2 个 vector，时间复杂度 O(n)。

Main code：

void solve() {
    n = read(), k = read();
    for(int i = 1; i <= n; i++) {
        a[i] = read() + 2e6;
        vec[a[i]].eb(-1), vec[a[i] + k].eb(1);
    }
    int ans = 0;
    for(int i = 0; i <= 4000000; i++) 
        if(vec[i].size()) {
            int res = 0, sum = 0;
            for(auto &x : vec[i]) if(x == -1) res++;
            ans = max(ans, res);
            for(auto &x : vec[i]) {
                sum = max(sum + x, x);
                ans = max(ans, res + sum);
            }
        }
    printf("%d\n", ans);
}