思路题--CF1082E Increasing Frequency

传送门

大意就是给你$n$n个数，你可以选择一段区间加上某个值（可正负），问操作完之后$C$C出现的次数最大是多少？

我觉得我的做法很巧妙！首先要知道一段区间加上某个值以后这个区间原来$=C$=C的数会变，而对$C$C的贡献一定都是一个数而且$a[l]=a[r]=$a[l]=a[r]=这个数（显然）

因为权值都比较小，然后记录$mx[a[i]]$mx[a[i]]表示某个权值对答案的最大贡献，还要一个$sum[i]$sum[i]表示$1-i$1−i的$C$C的个数（原来序列中）

显然$mx[a[i]]=max\begin{cases}sum[i]+1\\mx[a[i]]+1\end{cases}$mx[a[i]]=max{sum[i]+1mx[a[i]]+1​

$ans=max\{mx[a[i]]+sum[n]-sum[i]\}$ans=max{mx[a[i]]+sum[n]−sum[i]}

到此就结束了，是不是特别简单$qwq$qwq

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 500005
using namespace std;
int n,c,a[maxn],pre[maxn],mx[maxn],ans,sum[maxn];

inline int rd(){
	int x=0,f=1;char c=getchar();
	while(c<'0' || c>'9') f=c=='-'?-1:1,c=getchar();
	while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();
	return x*f;
}
inline int max(int x,int y){return x>y?x:y;}

int main(){
	n=rd(); c=rd();
	for(int i=1;i<=n;i++){
		a[i]=rd();
		if(a[i]==c) sum[i]=1;
	}
	for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
	ans=sum[n];
	for(int i=1;i<=n;i++){
		if(a[i]==c) continue;
		mx[a[i]]=max(sum[i]+1,mx[a[i]]+1);
		ans=max(ans,mx[a[i]]+sum[n]-sum[i]);
	}
	printf("%d\n",ans);
	return 0;
}