[CF1082E] Increasing Frequency

Description

给定一个长度为 \(n\) 的数列 \(a\) ，你可以任意选择一个区间 \([l,r]\) ，并给区间每个数加上一个整数 \(k\) ，求这样一次操作之后数列中最多有多少个数等于 \(c\)。

\(n,c,a_i\leq 10^5\)

Solution

假设当前选择区间的右端点为 \(r\)，那我们要强制将 \(a_r\) 这个元素变为 \(c\)，不然可以通过让右端点 \(-1\) 使答案变得不劣。

同理，如果我们左端点 \(l\) 的元素 \(a_l\) 也要让其强制等于 \(a_r\)，不然同样可以通过让左端点 \(+1\) 使答案变的不劣。

所以这个性质告诉我们选中的区间 \([l,r]\) 一定满足 \(a_l=a_r\)。

这启发我们对于每种取值分开做

设 \(f(x)\) 是右端点为 \(x\) 时最多有多少个元素取到 \(c\) 。

考虑列出 \(DP\) 式

\(f(x)=\max \left\{pre(las-1)+count(las,x)+suf(x+1)\right\}\)，其中 \(pre(i)\) 表示从 \(1\sim i\) 有多少个元素为 \(c\)，同理 \(suf(i)\) 表示从 \(i\sim n\) 有多少个元素为 \(c\), \(count(l,r)\) 表示在区间 \([l,r]\) 里有多少个元素等于这个区间的端点即 \(a_r\)。

发现如果拿 \(vector\) 存的话这是一个单调队列优化 \(DP\) 的标准式子

随便优化一下就吼了

Code

#include<bits/stdc++.h>

using std::min;

using std::max;

using std::swap;

using std::vector;

typedef double db;

typedef long long ll;

#define pb(A) push_back(A)

#define pii std::pair<int,int>

#define all(A) A.begin(),A.end()

#define mp(A,B) std::make_pair(A,B)

const int N=5e5+5;

vector<int> v[N];

int n,m,val[N],vis[N],q[N],hd;

int pre[N],suf[N],tot[N],tail;

int getint(){

    int X=0,w=0;char ch=getchar();

    while(!isdigit(ch))w|=ch=='-',ch=getchar();

    while( isdigit(ch))X=X*10+ch-48,ch=getchar();

    if(w) return -X;return X;

}

signed main(){

    n=getint(),m=getint();

    for(int i=1;i<=n;i++)

        val[i]=getint(),pre[i]=pre[i-1]+(val[i]==m),v[val[i]].pb(i);

    for(int i=n;i;i--)

        suf[i]=suf[i+1]+(val[i]==m);

    int ans=0;

    for(int i=1;i<=n;i++){

        if(!vis[val[i]]){

            vis[val[i]]=1;

            hd=1,tail=0;

            for(int j=0;j<v[val[i]].size();j++){

                while(hd<=tail and pre[ v[ val[i] ][ j ] -1 ]-j>=pre[ v[ val[i] ][ q[tail] ] -1 ]-q[tail]) tail--;

                q[++tail]=j;

                if(hd<=tail) ans=max(ans,pre[ v[ val[i] ][ q[hd] ] -1 ]+j-q[hd]+1+suf[ v[ val[i] ][ j ] +1 ]);

            }

        }

    } printf("%d\n",ans);

    return 0;

}