CF1446D Frequency Problem解题报告

解题报告

CF1446D1 Frequency Problem (Easy Version)&CF1446D2 Frequency Problem (Hard Version)解题报告：

更好的阅读体验

题意

• 给定一个长度为$n$的序列，定义好的序列为众数不唯一的序列，求最长的好的连续子序列。
• 数据范围：$1\leqslant n\leqslant 2\times 10^5$，$1\leqslant a_i\leqslant n$，对于Easy Version，$a_i\leqslant 100$。

分析

首先有一个结论：最长的众数不唯一的子序列一定包含整个序列的众数。

反证法：设整个序列的众数为$x$，如果这个子序列中众数不含有$x$，那么我们尝试每次给这个子序列扩展一个位置（如果扩展不了那么众数一定含有这个$x$），因为$x$为整个序列的众数，每一次扩展会最多让$x$增加$1$，所以总有一个时间$x$的数量会等于当前序列众数的数量，此时这个序列满足条件，且它一定优于原来的序列。

有了这个结论，我们先求得整个序列的众数$x$，如果众数不唯一，那么答案就是$n$，否则我们继续分析：

先考虑Easy Version，因为$a_i$的值域为$[1,100]$，所以我们直接枚举这个众数（设为$y$），然后重构一个新序列$b$：

• 当$a_i=x$时，$b_i=1$；
• 当$a_i=y$时，$b_i=-1$；
• 否则，$b_i=0$。

对于一个满足条件的序列，它的$x$出现次数与$y$的出现次数一定相等，因此我们可以统计所有$b$之和为$0$的序列进答案。

但是这里有一个疑问：如果在某一个区间中存在一个数$z$，出现次数比$x$和$y$均多，那这样的序列是否合法？

还是可以用上面的那种扩展的方法，发现一定存在一个更长的序列众数为$x,z$，且比刚才的序列更优，因此刚刚的序列被统计了也不会对最终答案造成影响。

这样我们就用$O(maxa\times n)$的复杂度解决了Easy Version。

对于Hard Version，观察数据范围，我们可以考虑进行根号分治。

设定一个阈值$S$，对于出现次数大于$S$的数字，它的个数一定不会超过$\frac{n}{S}$，因此我们可以用一个$\text{vector}$存下所有出现次数大于$S$的数字，然后用Easy Version的方法暴力统计答案，时间复杂度$O(n\sqrt{n})$。

然后，对于出现次数小于等于$S$的数字，我们很显然可以枚举这个出现次数（设为$i$），然后对于整个序列做一遍$\text{two pointer}$，里面维护所有数的出现次数和出现次数的出现次数，只要出现次数$i$的出现次数大于等于$2$，我们就统计这个答案。这样我们可以用$O(n\sqrt{n})$的复杂度解决问题。

时间复杂度：$O(n\sqrt{n})$。

代码

Easy Version:

#include<stdio.h>
#define inf 1000000000
const int maxn=200005,maxk=105;
int n,maxx,cnt,ans;
int a[maxn],tot[maxk],sum[maxn],t[maxn*2];
inline int min(int a,int b){
    return a<b? a:b;
}
inline int max(int a,int b){
    return a>b? a:b;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        tot[a[i]]++;
    }
    for(int i=1;i<=100;i++){
        if(tot[i]==maxx)
            cnt++;
        if(tot[i]>maxx)
            cnt=1,maxx=tot[i];
    }
    if(cnt>1){
        printf("%d\n",n);
        return 0;
    }
    for(int i=1;i<=100;i++)
        if(tot[i]==maxx){
            maxx=i;
            break;
        }
    for(int i=1;i<=100;i++){
        for(int j=1;j<=n;j++)
            sum[j]=sum[j-1]+(a[j]==i? -1:(a[j]==maxx? 1:0));
        for(int j=-n;j<=n;j++)
            t[n+j]=inf;
        for(int j=1;j<=n;j++){
            ans=max(ans,j-t[n+sum[j]]+1);
            t[n+sum[j-1]]=min(t[n+sum[j-1]],j);
        }
    }
    printf("%d\n",ans);
    return 0;
}

Hard Version

#include<stdio.h>
#include<math.h>
#include<vector>
#define inf 1000000000
using namespace std;
const int maxn=200005,maxt=505;
int n,maxx,cnt,ans,S,val;
int a[maxn],tot[maxn],sum[maxn],t[maxn*2],cnt1[maxn],cnt2[maxn];
vector<int>v;
inline void modify(int x,int v){
    cnt2[cnt1[x]]--;
    cnt1[x]+=v;
    cnt2[cnt1[x]]++;
}
int main(){
    scanf("%d",&n),S=sqrt(n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        tot[a[i]]++;
    }
    for(int i=1;i<=n;i++){
        if(tot[i]==maxx)
            cnt++;
        if(tot[i]>maxx)
            cnt=1,maxx=tot[i];
    }
    if(cnt>1){
        printf("%d\n",n);
        return 0;
    }
    for(int i=1;i<=n;i++){
        if(tot[i]==maxx)
            val=i;
        else if(tot[i]>S)       
            v.push_back(i);
    }
    for(int i=0;i<v.size();i++){
        int k=v[i];
        for(int j=1;j<=n;j++)
            sum[j]=sum[j-1]+(a[j]==k? -1:(a[j]==val? 1:0));
        for(int j=-n;j<=n;j++)
            t[n+j]=inf;
        for(int j=1;j<=n;j++){
            ans=max(ans,j-t[n+sum[j]]+1);
            t[n+sum[j-1]]=min(t[n+sum[j-1]],j);
        }
    }
    for(int i=1;i<=S;i++){
        for(int j=1;j<=n;j++)
            cnt1[j]=cnt2[j]=0;
        int l=1,r=0;
        while(r<n){
            r++,modify(a[r],1);
            while(cnt1[a[r]]>i)
                modify(a[l],-1),l++;
            if(cnt2[i]>=2)
                ans=max(ans,r-l+1);
        }
    }
    printf("%d\n",ans);
    return 0;
}