CF1082E Increasing Frequency (multiset+乱搞+贪心）

题目大意：

\(给你n个数a_i,给定一个m，你可以选择一个区间[l,r],让他们区间加一个任意数，然后询问一次操作完之后，最多能得到多少个m\)

QWQ

考场上真的**

想了好久都不会，直到考试快结束才知道怎么做。

首先，根据题目，我们可以得知，假设我们修改了\([l,r]\)这个区间，那么最后的\(ans\)就应该是总的m的个数，减去区间中m的个数，加上区间内的众数的个数

QWQ

那么我们考虑怎么来处理这个。

首先，每个数字之间都是独立的。

所以我们可以预处理每一个数字出现的位置。

然后假设当前我们要计算的数字是\(x\)

那么，我们可以先对于所有出现的位置\(i\)，求一个\([pos_1,pos_i]\)的答案QWQ

转移的式子也是比较显然。

\[dp[i]=di[i-1]+1-(sum_m)
\]

其中\(sum_m\)表示这段区间中的m的个数，这个可以用前缀和来维护

dp[j]=dp[j-1]+1-(sum[v[i][j]]-sum[v[i][j-1]]);

那么既然求出来这个东西，我们考虑左端点每移动一个，相当于对所有的右端点的区间加一个释放出来的贡献，也就是m的个数-1

所以说，我们现在需要一个能支持插入，删除，后缀修改，\(求max\)的一个数据结构

很自然能想到\(multiset\)，插入删除和max就不说了，后缀修改的话，我们只需要维护一个\(delta\)表示改变量，对于每个元素，调用的时候都\(+delta\)就解决了

QWQ

给代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<map>

#include<set>

#define mk makr_pair

#define ll long long

using namespace std;

inline int read()

{

  int x=0,f=1;char ch=getchar();

  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}

  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

  return x*f;

}

const int maxn = 5e5+1e2;

int n,a[maxn];

int m;

int sum[maxn];

vector<int> v[maxn];

int cnt;

int vis[maxn];

int dp[maxn];

int ans;

int main()

{

  n=read(),m=read();

  for (int i=1;i<=n;i++) v[i].push_back(0);

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

  {

    a[i]=read();

    if (!vis[a[i]])

    {

     ++cnt;

        vis[a[i]]=cnt;

 }

 v[vis[a[i]]].push_back(i);

  }

  for (int i=1;i<=n;i++) if(a[i]==m) sum[i]=1;

  for (int i=1;i<=n;i++) sum[i]+=sum[i-1];

  ans=sum[n];

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

  {

   if (a[v[i][1]]==m) continue;

   int num = v[i].size();

   multiset<int> s;

   dp[1]=1;

   s.insert(1);

   for (int j=2;j<num;j++)

   {

    dp[j]=dp[j-1]+1-(sum[v[i][j]]-sum[v[i][j-1]]);

    //cout<<j<<" "<<dp[j]<<endl;

    s.insert(dp[j]);

 }

 ans=max(ans,(*(s.rbegin()))+sum[n]);

 int j=1;

 int delta=0;

 while (j<num-1)

 {

  s.erase(s.find(dp[j]));

  j++;

  delta+=sum[v[i][j]]-sum[v[i][j-1]]-1;

  ans=max(ans,(*(s.rbegin()))+delta+sum[n]);

 }

  }

  cout<<ans;

  return 0;

}

巴特西

CF1082E Increasing Frequency (multiset+乱搞+贪心）

最新文章

热门文章