题目链接：CodeForces-1082E Increasing Frequency
有$n$个元素，第$i$个元素的值为$a_i$，你可以选择一个区间$[l,r]$，并将这个区间的每个元素的值都加上$k$ ($k$为任意值，包括0和负数)，问你在进行一次修改后，能让这个序列中最多存在几个值为$c$的元素。
我们考虑将区间$[l,r]$中所有的$x$都修改为$c$，则只需让这个区间中的每一个元素都加上$c-x$，此时区间中所有的$x$都会变成$c$，而$c$则变成了$c+c-x$。
记$f(i)$为区间$[1,i]$中有多少个元素的值为$c$，记$g(x,i)$为区间$[1,i]$中有多少个元素的值为$x$。
则我们修改某个区间$[l,r]$中的$x$的时候，整个序列中$c$的个数由$f(n)$变为了$f(l-1)+f(n)-f(r)+g(x,r)-g(x,l-1)$。
注意到对于每一个固定的$x$和$r$，$f(n),f(r),g(x,r)$均为定值，问题就转化为对每一个$x$和$r$，求$max\{f(l-1)-g(x,l-1) \}$，这样一来就可以$O(n)$进行dp了。
实际实现中，我们不需要用二维数组表示$g(x, i)$，由于其不同的$x$之间无关，还有前缀和的性质，用一个变量更新即可。
#include <iostream> #include <cstdio> #include <vector> #include <map> using std::map; using std::vector; using std::max; const int maxn = 500010; int f[maxn]; int main() { int n, c, x; while (~scanf("%d %d", &n, &c)) { map<int, vector<int> > mp; for (int i = 1; i <= n; i++) { scanf("%d", &x); f[i] = f[i-1] + (x == c); mp[x].push_back(i); } int ans = 0; for (auto cur : mp) { int mx = 0, g = 0; for (auto pos : cur.second) { mx = max(mx, f[pos-1] - g++); ans = max(ans, f[n] - f[pos] + g + mx); } } printf("%d\n", ans); } return 0; }
CodeForces-1082E Increasing Frequency
原文：https://www.cnblogs.com/kangkang-/p/11296246.html
