zcmimi's blog

查看原题

点击跳转

题意: 给出一个长度为n序列a,m次询问,每次询问区间[l,r]里出现次数最多的数. 若有多个,输出最小的.

如果是严格区间众数可以用主席树,这里要求找到出现次数最多的数,只能使用分块

先对序列进行离散化

预处理:

  1. s[i][j]表示前i个块中j出现了几次
  2. p[i][j]表示第i块到第j块中出现次数最多的数,P[i][j]表示次数

复杂度\mathcal O(n\log n)

对于一个询问[l,r]

l,r在同一个块或相邻块,那么暴力求解

否则枚举块外的数,每个数的出现次数为块内的+块外的,与块内已经预处理出的答案比较,更新答案

#include<bits/stdc++.h>
const int N=44011;
int n,q,blk,a[N],b[N],c[N];
int cnt[N],s[222][N],p[222][222],P[222][222],bl[N],L[222],R[222];
void cmin(int&x,int y){if(y<x)x=y;}
void init(){
    for(int i=1;i<=n;++i)scanf("%d",a+i),b[i]=a[i];
    std::sort(b+1,b+n+1);
    int tt=std::unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i)c[i]=std::lower_bound(b+1,b+tt+1,a[i])-b;

    blk=sqrt(n);
    for(int i=1;i<=n;++i)bl[i]=(i-1)/blk+1;
    for(int i=1;i<=bl[n];++i)
        L[i]=R[i-1]+1,R[i]=R[i-1]+blk;
    R[bl[n]]=n;
    for(int i=1;i<=bl[n];++i){
        for(int j=i,mx=0,mxv=0;j<=bl[n];++j){
            for(int k=L[j];k<=R[j];++k)
                if(++cnt[c[k]]>mxv)mxv=cnt[c[k]],mx=c[k];
                else if(cnt[c[k]]==mxv)cmin(mx,c[k]);
            p[i][j]=mx,P[i][j]=mxv;
        }
        for(int j=L[i];j<=n;++j)--cnt[c[j]];

        for(int j=1;j<=n;++j)s[i][c[j]]=s[i-1][c[j]];
        for(int j=L[i];j<=R[i];++j)++s[i][c[j]];
    }
}
int solve(int l,int r){
    int ans=0;
    if(bl[r]-bl[l]<2){
        for(int i=l;i<=r;++i)cnt[c[i]]=0;
        for(int i=l;i<=r;++i)
            if(++cnt[c[i]]>cnt[ans])ans=c[i];
            else if(cnt[c[i]]==cnt[ans])cmin(ans,c[i]);
    }
    else{
        ans=p[bl[l]+1][bl[r]-1];cnt[ans]=0;
        for(int i=l;bl[i]==bl[l];++i)cnt[c[i]]=0;
        for(int i=r;bl[i]==bl[r];--i)cnt[c[i]]=0;
        for(int i=l;bl[i]==bl[l];++i)++cnt[c[i]];
        for(int i=r;bl[i]==bl[r];--i)++cnt[c[i]];
        int mx=0,mxv=0;
        for(int i=l;bl[i]==bl[l];++i){
            int t=cnt[c[i]]+s[bl[r]-1][c[i]]-s[bl[l]][c[i]];
            if(t>mxv)mx=c[i],mxv=t;
            else if(t==mxv)cmin(mx,c[i]);
        }
        for(int i=r;bl[i]==bl[r];--i){
            int t=cnt[c[i]]+s[bl[r]-1][c[i]]-s[bl[l]][c[i]];
            if(t>mxv)mx=c[i],mxv=t;
            else if(t==mxv)cmin(mx,c[i]);
        }
        if(mxv>cnt[ans]+P[bl[l]+1][bl[r]-1])ans=mx;
        else if(mxv==cnt[ans]+P[bl[l]+1][bl[r]-1])cmin(ans,mx);
    }
    return b[ans];
}
int main(){
    scanf("%d%d",&n,&q);
    init();
    int l,r,la=0;
    while(q--){
        scanf("%d%d",&l,&r);
        l=(l+la-1)%n+1,r=(r+la-1)%n+1;
        if(l>r)std::swap(l,r);
        printf("%d\n",la=solve(l,r));
    }
}
LG 4168 [Violet]蒲公英
comment评论
Search
search