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

· · 题解

题意:@#%^%@#%#$^

这个题目我们不看它

看下面这个:

给你n个数,m次询问区间[l,r]中众数的出现次数

它萌为什么是一样的呢?

就比如说这个数列1,1,1,2,2,4,5,6,6,7

我们把它排成一段一段的递增序列可以使rp掉的最少

就变成了1,2,4,5,6,7,1,2,6,1共掉3点rp

然后发现递增序列的个数就等于区间众数的出现次数

于是莫队解决它

加入一个数时,把$Ans$和$cnt$取个$Max

删除一个数时,如果有t[cnt]==1&&cnt==Ans那么Ans--

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int re(){
    int x=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*w;
}
int n,m,B,len,Ans,a[N],d[N],b[N],t[N],cnt[N],ans[N];
struct Q{int l,r,id;}q[N];
bool cmp(Q x,Q y){
    if(b[x.l]==b[y.l])
        if(b[x.l]&1)return x.r<y.r;
        else return x.r>y.r;
    return b[x.l]<b[y.l];
}
void add(int i){
    t[cnt[a[i]]]--;
    t[++cnt[a[i]]]++;
    Ans=max(Ans,cnt[a[i]]);
}
void del(int i){
    t[cnt[a[i]]]--;
    if(cnt[a[i]]==Ans&&!t[cnt[a[i]]])Ans--;
    t[--cnt[a[i]]]++;
}
int main(){
    n=re(),m=re();B=sqrt(n);
    for(int i=1;i<=n;i++){
        d[i]=a[i]=re();
        b[i]=(i-1)/B+1;
    }
    sort(d+1,d+n+1);len=unique(d+1,d+n+1)-d-1;
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(d+1,d+len+1,a[i])-d;
    for(int i=1;i<=m;i++)
        q[i]=(Q){re(),re(),i};
    sort(q+1,q+m+1,cmp);
    for(int i=1,l=1,r=0;i<=m;i++){
        while(r<q[i].r)add(++r);
        while(r>q[i].r)del(r--);
        while(l<q[i].l)del(l++);
        while(l>q[i].l)add(--l);
        ans[q[i].id]=Ans;
    }
    for(int i=1;i<=m;i++)printf("%d\n",-ans[i]);
    return 0;
}