CF1082E Increasing Frequency

CF1082E Increasing Frequency

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

\(n,\ c,\ a_i\in[1,\ 5\times 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;
}