1082E. Increasing Frequency

记录左边更优方案的方法很有趣

一开始没想出来

//cyc
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mst(a) memset(a,0,sizeof a)
using namespace std;
typedef pair<int,int> pii;
/*
  もう一回、もう一回！
*/
const int maxn=5e5+5;
const int maxp=1e6+5;
int a[maxn];
int vis[maxn];
int suf[maxn];
int pref[maxn];
int lans[maxn];
int lst[maxn];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,c;
    cin>>n>>c;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        pref[i]=pref[i-1];
        if(a[i]==c){
            pref[i]++;
        }
    }
    for(int i=n;i>=1;i--){
        suf[i]=suf[i+1];
        if(a[i]==c){
            suf[i]++;
        }
    }

    for(int i=1;i<=n;i++){
        int p=lst[a[i]];
        lans[i]=pref[i-1]+1;
        lans[i]=max(lans[i],lans[p]+1);
        lst[a[i]]=i;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,lans[i]+suf[i+1]);
    }
    cout<<ans<<endl;
}