区间众数，分块

淡淡的烟草味﹌ 2023-06-10 15:30 4阅读 0赞

第一次过了一个洛谷黑题，区间众数

洛谷：4168

代码：

#include<bits/stdc++.h>
    using namespace std;
    using ll =long long;
    const int M=4e4+5,K=210;
    struct Node{ll num,val;}p[K][K],e;
    ll d[M],n,m,blo,L[K],R[K],B[M],sum[K][M],b[M],pos[M];
    void prework(){
        for(ll i=1;i<=blo;i++){
            e.num=e.val=0;
            memset(B,0,sizeof(B));
            for(ll j=i;j<=blo;j++){
    
                for(ll k=L[j];k<=R[j];k++){
                    B[d[k]]++;
                    if(e.num<B[d[k]]){
                        e.num=B[d[k]];
                        e.val=d[k];
                    }else if(e.num==B[d[k]]) e.val=min(e.val,d[k]);
                }
                p[i][j]=e;
            }
        }
        for(ll i=1;i<=blo;i++){
            for(ll j=1;j<=b[0];j++)sum[i][j]=sum[i-1][j];
            for(ll j=L[i];j<=R[i];j++) sum[i][d[j]]++;
        }
    }
    int main(){
        scanf("%lld%lld",&n,&m);
        for(ll i=1;i<=n;i++)  scanf("%lld",&d[i]),b[i]=d[i];
    
        sort(b+1,b+n+1);        b[0]=1;
        for(ll i=2;i<=n;i++)   if(b[i]!=b[i-1]) b[++b[0]]=b[i];
        for(ll i=1;i<=n;i++)   d[i]=lower_bound(b+1,b+b[0]+1,d[i])-b;
    
        blo=sqrt(n);
        for(ll i=1;i<=blo;i++){
            L[i]=(i-1)*blo+1;
            R[i]=i*blo;
        }
        if(R[blo]<n){
            blo++;
            R[blo]=n;
            L[blo]=R[blo-1]+1;
        }
        for(ll i=1;i<=blo;i++)
            for(ll j=L[i];j<=R[i];j++)
                pos[j]=i;
    
        prework();
    
        ll l,r,pl,pr,las=0;
        while(m--){
            scanf("%lld%lld",&l,&r);
    
            l=(l+las-1)%n+1;
            r=(r+las-1)%n+1;
            if(l>r)
                swap(l,r);
    
            pl=pos[l];
            pr=pos[r];
            e.num=e.val=0;
    
            if(pr-pl<=2){
                for(ll i=l;i<=r;i++) B[d[i]]=0;
                for(ll i=l;i<=r;i++){
                    B[d[i]]++;
                    if(e.num<B[d[i]]) e.num=B[d[i]],e.val=d[i];
                    else if(e.num==B[d[i]]) e.val=min(e.val,d[i]);
                }
            }else{
                B[p[pl+1][pr-1].val]=0;
                for(ll i=l;i<=R[pl];i++)B[d[i]]=0;
                for(ll i=L[pr];i<=r;i++)B[d[i]]=0;
    
                for(ll num,i=l;i<=R[pl];i++){
                    B[d[i]]++;
                    num=B[d[i]] + sum[pr-1][d[i]] - sum[pl][d[i]];
                    if(e.num< num) e.num=num,e.val=d[i];
                    else if(e.num==num) e.val=min(d[i],e.val);
                }
                for(ll num,i=L[pr];i<=r;i++){
                    B[d[i]]++;
                    num=B[d[i]] + sum[pr-1][d[i]] - sum[pl][d[i]];
                    if(e.num<num)  e.num=num,e.val=d[i];
                    else if(e.num==num)e.val=min(d[i],e.val);
                }
                if(e.num < B[ p[pl+1][pr-1].val ]+p[pl+1][pr-1].num)e.num=B[p[pl+1][pr-1].val]+p[pl+1][pr-1].num,e.val=p[pl+1][pr-1].val;
                else if(e.num==B[p[pl+1][pr-1].val]+p[pl+1][pr-1].num) e.val=min(e.val,p[pl+1][pr-1].val);
            }
            printf("%lld\n",las=b[e.val]);
        }
        return 0;
    }

快退役了 ，退役前给自己的一个惊喜