CF1082E Increasing Frequency

CF1082E Increasing Frequency

给定一个序列 (a_i) ，可以选择任意一个区间 ([l, r]) ，并给区间每个数加 (k) （ (k) 为任意整数），求一次操作后序列中最多有多少个数等于 (c)

(n, c, a_iin[1, 5 imes 10^5])

贪心

---

令 (cnt(l, r, k)) 为区间 ([l, r]) 中 (k) 的个数，则答案为 (max{cnt(1, l-1, c)+cnt(l, r, d)+cnt(r+1, n, c)}) ，可以化简为 (max{cnt(1, n, c)+cnt(l, r, d)-cnt(l, r, c)})

现在的目的就是最大化 (cnt(l, r, d)-cnt(l, r, c)) ，可以枚举 (d) 并进行计算

时间复杂度 (O(n))

代码

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

const int maxn = 5e5 + 10;
int n, c, a[maxn], sum[maxn];

vector <int> vec[maxn];

int main() {
  scanf("%d %d", &n, &c);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    vec[a[i]].push_back(i);
    sum[i] = sum[i - 1] + (a[i] == c);
  }
  int ans = 0;
  for (int i = 1; i < 500001; i++) {
    int val = 1 << 30, cnt = 0, res = 0;
    for (int pos : vec[i]) {
      val = min(val, cnt++ - sum[pos - 1]);
      res = max(res, cnt - sum[pos] - val);
    }
    ans = max(ans, res);
  }
  printf("%d", ans + sum[n]);
  return 0;
}