题解 P1997 【faebdc 的烦恼】

· · 题解

P1997 faebdc 的烦恼

题意分析：让您求出区间众数出现的次数。

区间问题考虑莫队。

加入操作非常好写，如果 \text{x} 的出现个数大于当前答案，直接更新即可。

删除操作要考虑删掉的 \text{x} 出现次数是不是会影响答案。

分类讨论

  1. 当出现次数小于当前 \text{ans} ，对答案没有影响；
  2. 当出现次数等于当前 \text{ans} ，且只有这个数出现了 \text{ans} 次， \text{ans} 减一；
  3. 当出现次数等于当前 \text{ans} ，且不止一个数出现了 \text{ans} 次，对答案没有影响。

综上所述，我们需要开一个辅助数组记录出现了 i 次的数的个数。（可能有点拗口，没明白建议多读几遍）如果只有一个数 \text{ans} 就需要减一。

注意事项： 值域中有负数，但是并不大，我们懒得写离散化，于是开双倍空间然后全体起立加上 \max(n) ，也就是 10^5 。

一个小优化：没有必要在一个数字出现次数增加时改变之前的辅助数组记录的数值，因为求的是 \max ，之前的不会对答案造成影响，在删除的时候也会被删掉。

还没明白就看看代码吧。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

const int N=1e5+10;

int n,m,a[N],cnt[N << 1],len,bl[N],ans[N*2],maxn,sum[N];//cnt[i]:数字i出现的个数；sum[i]:出现次数为i的数字个数 
struct query
{
    int l,r,id;
    bool operator <(const query x) const {return bl[l]^bl[x.l]? l<x.l:bl[l]&1? r<x.r:r>x.r;}
} q[N << 1];

inline void add(int x)
{
    sum[++cnt[a[x]]]++;
    if(cnt[a[x]] > maxn) maxn=cnt[a[x]];
    return ;
}
inline void del(int x)
{
    if(sum[cnt[a[x]]] == 1 && maxn == cnt[a[x]]) maxn--;
    sum[cnt[a[x]]--]--;
    return ;
}

int main()
{
//  freopen("work.in","r",stdin); freopen("work.out","w",stdout);
    scanf("%d%d",&n,&m);
    len=sqrt(n);
    for(int i=1;i<=n;i++) {scanf("%d",&a[i]); a[i]+=N-10; bl[i]=(i-1)/len+1;}
    for(int i=1;i<=m;i++) {scanf("%d%d",&q[i].l,&q[i].r); q[i].id=i;}
    sort(q+1,q+1+m);
    int l=1,r=0;
    for(int i=1;i<=m;i++)
    {
        while(l > q[i].l) add(--l);
        while(r < q[i].r) add(++r);
        while(r > q[i].r) del(r--);
        while(l < q[i].l) del(l++);
        ans[q[i].id]=maxn;
    }
    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
//  fclose(stdin); fclose(stdout);
    return 0;
}

建议切完这题后做一下P3709 大爷的字符串题，在此安利一下本人关于这题的题解。

Thank you for your reading!

您的点赞和评论是对作者最好的支持！