E. Increasing Frequency 题解（完整整合版）

---

一、题目描述

时间限制： 2秒
内存限制： 256 MB

给定一个长度为 $n$ 的数组 $a$。你可以选择一个子段 $[l, r]$（$1 \le l \le r \le n$）和一个整数 $k$（可以为正数、负数或零），然后对该子段中的每个元素加上 $k$（即对于每个 $l \le i \le r$，令 $a_i := a_i + k$）。

问：经过一次这样的操作后，数组中值为 $c$ 的元素最多能有多少个？

输入

第一行包含两个整数 $n$ 和 $c$（$1 \le n \le 5 \cdot 10^5$，$1 \le c \le 5 \cdot 10^5$）——数组长度以及目标值 $c$。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 5 \cdot 10^5$）——数组 $a$。

输出

输出一个整数——经过上述操作后，值为 $c$ 的元素的最大可能数量。

样例

样例 1

输入：
6 9
9 9 9 9 9 9

输出：
6

样例 2

输入：
3 2
6 2 6

输出：
2

提示

• 样例 1：选择任意子段并取 $k = 0$，数组保持不变。
• 样例 2：选择子段 $[1, 3]$ 并取 $k = -4$，数组变为 $[2, -2, 2]$。

---

二、核心思路

问题转化

对于某个值 $v \neq c$，若我们选择 $k = c - v$，则操作区间内：

• 原本等于 $v$ 的元素会变成 $c$ → 收益 $+1$
• 原本等于 $c$ 的元素会变成 $c + (c - v) \neq c$ → 损失 $-1$
• 其他值不受影响，忽略

因此，对每个 $v \neq c$，问题转化为：

找一个区间，最大化区间内 v 的个数 - c 的个数。

最终答案：

$$\text{ans} = (\text{原数组中 } c \text{ 的总数}) + \max_{v \neq c}\Big(\max_{\text{区间}} (cnt_v - cnt_c)\Big) $$

括号内部至少为 $0$（可取 $k = 0$，什么也不做）。

---

Kadane 算法（最大子段和）

上述内层是经典的最大子段和问题：把 $v$ 看作 $+1$，$c$ 看作 $-1$，求最大连续子段和。

int maxSegment(const vector<int>& s) {
    int mx = -INF;
    int bal = 0;
    for (int i = 0; i < sz(s); i++) {
        bal = max(0, bal + s[i]);  // 若前缀和变负则丢弃
        mx = max(mx, bal);
    }
    return mx;
}

时间复杂度 $O(\text{序列长度})$。

---

高效构建序列

对每个 $v$ 显式构建完整 $+1/-1$ 序列再跑 Kadane 是 $O(n^2)$ 的，不可行。

优化： 利用 $c$ 的前缀和数组 cntC，将相邻 $v$ 之间夹着的所有 $c$ 合并为一个权值为 $-(\text{中间 } c \text{ 数量})$ 的元素。这样每个 $v$ 的序列长度与其出现次数成正比，总长度 $O(n)$。

构建过程：

1. 预处理 $c$ 的前缀和 cntC[i] = 前 $i$ 个元素中 $c$ 的个数。
2. 遍历数组，用 lst[v] 记录值 $v$ 上一次出现的位置。
3. 对当前 $a[i] = v$：
   • 压入 $-($上一次 $v$ 到当前位置之间的 $c$ 数量$)$
   • 压入 $+1$（当前 $v$）
4. 遍历结束后对每个 $v$ 补上最后一段到末尾的 $c$ 数量。

---

三、AC 代码

#include <bits/stdc++.h>
using namespace std;

const int INF = int(1e9);

int n, c;
vector<int> a;
vector<int> cntC;

int getCnt(int l, int r) {
    return cntC[r] - cntC[l];
}

int maxSegment(const vector<int>& s) {
    int mx = -INF;
    int bal = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        bal = max(0, bal + s[i]);
        mx = max(mx, bal);
    }
    return mx;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> c;
    a.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    cntC.assign(n + 1, 0);
    for (int i = 0; i < n; i++)
        cntC[i + 1] = cntC[i] + (a[i] == c);

    int cntDif = *max_element(a.begin(), a.end()) + 1;
    vector<vector<int>> segs(cntDif);
    vector<int> lst(cntDif, -1);

    for (int i = 0; i < n; i++) {
        segs[a[i]].push_back(-getCnt(lst[a[i]] + 1, i));
        lst[a[i]] = i;
        segs[a[i]].push_back(1);
    }
    for (int v = 0; v < cntDif; v++)
        segs[v].push_back(-getCnt(lst[v] + 1, n));

    int ans = 0;
    for (int v = 0; v < cntDif; v++) {
        if (v == c) continue;
        ans = max(ans, maxSegment(segs[v]));
    }

    cout << cntC[n] + ans << "\n";
    return 0;
}

---

四、复杂度分析

• 时间复杂度： $O(n + \max a_i)$。构建序列总长度 $O(n)$，所有 Kadane 总时间 $O(n)$。
• 空间复杂度： $O(n + \max a_i)$。

---