题目意思
至多进行一次操作,一个操作定义为将 \(i\in{[l,r]}\) 的 \(a_i = a_i + b\) 这个 \(b\) 自定,无限制,询问至多一次操作之后,至多有多少个 \(i\in{[1,n]}\) 满足 \(a_i=c\) 其中 \(c\) 为给定的一个数。
思路
首先我们考虑如果我们选定了 \({[l,r]}\),我们要怎么做才能让答案最大,首先 \(a_r\) 必须是区间众数,否则的话将右端点和左端点都移到最外面的区间众数一定是不劣的,发现我们肯定是让区间众数变成 \(c\),那么区间 \({[l,r]}\) 中的所有 \(a_i=c\) 的 \(a_i\) 都不可能是 \(c\) 了,所以假设我们区间外面有 \(num\) 个 \(i\) 满足 \(a_i=c\),区间内的众数数量为 \(num'\),则最多有 \(num+num'\) 个 \(c\),发现不好计算区间外有多少个 \(c\) 考虑转化,变成区间内众数数量减去区间内 \(c\) 的数量加上 \(c\) 的总数
具体的我们令 \(all\) 为 \(c\) 的总数,$sum_{i,j} 表示前 \(i\) 个数字,\(j\) 的出现次数,那么区间 \({[l,r]}\) 操作一次答案最大为 \(sum_{r,a_r}-sum_{l-1,a_r}-(sum_{r,c}-sum_{l-1,c})+all\),变化一下就是
因为我们 \(a_r=a_l\),所以对于每一个 \(i\) 记录一个 \(mn_i\) 表示 \(\max\limits_{j=1,a_j=a_i}^{j\le i}(sum_{j,c}-sum_{j,a_i})\),然后因为它就相当于从上一个 \(a_j=a_i\) 的位置新加入了一个节点,所以我们直接从上一个继承就可以了
tips:因为空间复杂度的问题,所以第一维要滚掉
代码
//好烦
#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cmath>
#define ll long longusing namespace std;
const int N=5e5+9;
int n,c,a[N],mn[N],mx[N],sum[N];int main(){int ans=INT_MIN;cin>>n>>c;for(int i=1;i<=n;i++){cin>>a[i];mn[a[i]]=max(mn[a[i]],sum[c]-sum[a[i]]);sum[a[i]]++;mx[a[i]]=max(mx[a[i]],sum[a[i]]-sum[c]+mn[a[i]]);}for(int i=1;i<N;i++)ans=max(ans,mx[i]+sum[c]);cout<<ans;return 0;
}