题解 P3709 【大爷的字符串题】

· · 题解

P3709 大爷的字符串题

题意分析

我们希望放进去的顺序是多个尽量长的严格上升序列。

显然有多少个严格上升序列答案就是多少，最后将它变成它的相反数即可。

设最后剩下来一些同样的数，那么答案就是这个剩下来的数的总个数。因为这些剩下的每一个放进去人品都会减少，而之前的序列中每一个都包含这个数。

这个数就是众数。于是问题转化成求区间众数出现的个数。

做法

考虑莫队。

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

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

分类讨论

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

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

需要离散化 。

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

还没明白就看看代码吧。

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

using namespace std;

const int N=2e5+10;

int n,m,a[N],cnt[N],len,bl[N],ans[N],maxn,sum[N];//cnt[i]:数字i出现的个数；sum[i]:出现次数为i的数字个数
vector <int> v; 
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];

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]); v.push_back(a[i]); bl[i]=(i-1)/len+1;}
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());//离散化
    for(int i=1;i<=n;i++) a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+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;
}

弱化版P1997 faebdc 的烦恼，不需要离散化，在此安利一下本人关于这题的题解。

Thank you for your reading!

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