CF1082E Increasing Frequency

题意
给你一个长度为n的数列a，你可以任意选择一个区间[L,R]并给区间每个数加上一个整数k，求这样一次操作后数列中最多有多少个数等于c。

写法比较巧妙的一个贪心题。

显然可以想到相同的数字要放在一起来维护。

具体可以对每种数字开一个vector。然后枚举左端点，此时右端点的贡献是一个只与右端点下标有关的式子。
差不多长这个样子

(id[r]-id[l-1])-(s[r]-s[l-1])

显然可以用线段树来维护。

以上是自闭青年的做法。

考虑文艺青年会怎么做：

既然一个区间的贡献可以直接计算，那么就直接O(n)扫描一遍，用dp数组记录当前每一种数字可以取到的价值最大的前缀。

枚举到第i位时，显然可以对dp[a[i]]做一个更新。

dp[a[i]]=max(dp[a[i]],s[i-1])+1;

然后，对每个时刻进行答案更新即可。ans=max(ans,dp[i]+s[n]-s[i]);

#include<iostream>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#define N 1100000
#define L 1000000
#define eps 1e-7
#define inf 1e9+7
#define ll long long
using namespace std;
inline int read()
{
    char ch=0;
    int x=0,flag=1;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*flag;
}
int a[N],s[N],dp[N];
int main()
{
    int n=read(),k=read(),ans=0;
    for(int i=1;i<=n;i++)a[i]=read(),s[i]=s[i-1]+(a[i]==k);
    for(int i=1;i<=n;i++)
    {
        dp[a[i]]=max(dp[a[i]],s[i-1])+1;
        ans=max(ans,dp[a[i]]+s[n]-s[i]);
    }
    printf("%d",max(ans,s[n]));
    return 0;
}