P3709 大爷的字符串题

· · 题解

P3709 大爷的字符串题

题目翻译：

这道题充分的体现了信竞对语文的要求之高，读一个小时也读不懂 给出一个长度为 n 的序列，m 次询问，求区间 [l,r] 间的众数的个数。

思路：

又是求区间值，考虑莫队。发现我们只需要用莫队来维护区间内每一种数的个数，然后找到数量最多的一个即为答案。

如何删减点？cnt[i] 表示第 i 个数出现了几次 ,t[i] 表示出现 i 次的数有几个。那增加点的时候，直接判断取较大值，删点时要判断是否为出现次数最多的数，若是则要将答案减一

int Ans;
void add(int i){
    t[cnt[i]]--;
    t[++cnt[i]]++;
    Ans=max(Ans,cnt[i]);
}
void del(int i){
    t[cnt[i]]--;
    if(cnt[i]==Ans && !t[cnt[i]])Ans--;
    t[--cnt[i]]++;
}

由于本题的 a[i]较大则需要离散化一下。否则会 RE

完整代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int a[N],cnt[N],b[N],d[N];
struct query{
    int l,r,id,k;
}q[N];
int ans[N];
int t[N];
bool cmp(query x,query y){
    if(x.k!=y.k){
        return x.k<y.k;
    }
    else if(x.k&1){
        return x.r<y.r;
    }
    else{
        return x.r>y.r; 
    }
}
int Ans;
void add(int i){
    t[cnt[i]]--;
    t[++cnt[i]]++;
    Ans=max(Ans,cnt[i]);
}
void del(int i){
    t[cnt[i]]--;
    if(cnt[i]==Ans && !t[cnt[i]])Ans--;
    t[--cnt[i]]++;
}
signed main(){

    int n,m;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&d[i]);
        a[i]=d[i];
    }
    sort(d+1,d+n+1);
    int lenth=unique(d+1,d+n+1)-d-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(d+1,d+lenth+1,a[i])-d;
    }

    int len=sqrt(n);
    for(int i=1;i<=m;i++){
        int l,r;
        scanf("%lld%lld",&l,&r);
        q[i]={l,r,i,l/len};
    }

    sort(q+1,q+m+1,cmp);
    int l=1,r=0;
    for(int i=1;i<=m;i++){
        int ll=q[i].l;
        int rr=q[i].r;
        while(l>ll)add(a[--l]);
        while(r<rr)add(a[++r]);
        while(l<ll)del(a[l++]);
        while(r>rr)del(a[r--]);
        ans[q[i].id]=Ans;
    }
    for(int i=1;i<=m;i++){
        printf("%lld\n",-ans[i]);
    }
    return 0;
}

莫队讲解