cf[educational55]E

发表于 | 阅读数 次

链接:cf[educational55]E

题解

  • 枚举右端点r，考虑最优的左端点l所在的位置，只需要考虑l左边c的个数以及l右边该数的个数。
  • t[x]表示右端点是x这个数时的最优左端点，那么当前以a[i]为右端点时，考虑能否更新t[a[i]]为i-1
  • 更新条件显然是$$cnt[a[i]]-cntc+cnta[i]<cnt[a[i]]-cntc+cnta[i]
  • 那么显然我们可以直接维护a[i]的cnt[a[i]]-cnt[c]的最小值即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=1e6+7;
int n,x,c,ans,f[N],cnt[N];
int main(){
	scanf("%d%d",&n,&c);
	rep(i,1,n){
		scanf("%d",&x);
		f[x]=min(f[x],cnt[x]-cnt[c]);   
		cnt[x]++;
		ans=max(ans,cnt[x]-cnt[c]-f[x]);
	}
	printf("%d\n",ans+cnt[c]);
	return 0;
}