E. Increasing Frequency
题意
给你一个数列，你可以选择在[l,r]区间同时加或者减一个值，
在一次操作后，这个序列最多有多少个值等于c
做法
首先我们要想明白的是，a[l]一定是等于a[r]的
如果a[l]!=a[r]，那么我们肯定可以缩小这个区间，
因为只有首尾相等他们才能同时变成c，不然这个区间范围就可以缩小
那么我们知道首尾一定相同的话，n^2的做法就特别好实现
设数组sum[i]表示到i为止有多少个
设数组cnt[i][j]表示到i位置j这个数有多少个。
int ans=0;
for(int i=1;i<=n;i++)
{ans=max(ans,sum[n]+1-(a[i]==c);for(int j=1;j<i;j++){ if(a[i]==a[j]) ans=max(ans,(sum[n]-(sum[i]-sum[j-1]))+cnt[i][a[i]]-cnt[j-1][a[j]]);}
}
之后我们发现，更新ans的过程中,sum[n],sum[i],cnt[i][a[i]]sum[n],sum[i],cnt[i][a[i]]sum[n],sum[i],cnt[i][a[i]],我们都是可以通过i直接得到的
只有sum[j?1]?cnt[j?1][a[j]]sum[j-1]-cnt[j-1][a[j]]sum[j?1]?cnt[j?1][a[j]]是得不到的，而这个值有可以只由j就得到
所以我们只需要在遍历的过程中维护对于每个值来说的sum[j?1]?cnt[j?1][a[j]]sum[j-1]-cnt[j-1][a[j]]sum[j?1]?cnt[j?1][a[j]]的最大值即可
代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 5e5+5;
int a[maxn];
int maxx[maxn];
int sum[maxn];
int summ[maxn];
int main()
{
int n,c;scanf("%d%d",&n,&c);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++){
if(a[i]==c) sum[i]=sum[i-1]+1;else sum[i]=sum[i-1];}int ss=sum[n];int ans=sum[n];for(int i=1;i<=n;i++){
int id=a[i];if(summ[id]++==0) ans=max(ans,ss-(id==c)+1);else ans=max(ans,summ[id]-sum[i]+maxx[id]);maxx[id]=max(maxx[id],ss+sum[i-1]-summ[id]+1);}printf("%d\n",ans);return 0;
}