蒲公英样例没过求助

P4168 [Violet] 蒲公英

黑影洞人 @ 2022-09-09 14:18:43

#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 41451
using namespace std;
int tot,k,n,m,block,left[100],right[100],pos[N],cnt[50][50][N],f[50][50],num[50][50];
int a[N],b[N];
void lsh(int *a,int n){
    for(int i=1;i<=n;i++)b[i]=a[i];
    sort(b+1,b+n+1);k=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+k+1,a[i])-b;
}
void build(){
    block=(int)pow(1.0*n,2.0/3);
    tot=n/block;
    if(n%block)tot++;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),pos[i]=(i-1)/block+1;
    lsh(a,n);
    for(int i=1;i<=tot;i++){
        left[i]=(i-1)*block+1;
        right[i]=i*block;
    }
    right[tot]=n;
    for(int i=1;i<=tot;i++){
        for(int j=i;j<=tot;j++){
            for(int t=left[i];t<=right[j];t++)cnt[i][j][a[t]]++;
            for(int t=1;t<=k;t++){
                if(cnt[i][j][t]>f[i][j]||(cnt[i][j][t]==f[i][j]&&t<num[i][j])){
                    f[i][j]=cnt[i][j][t];
                    num[i][j]=t;
                }
            }
        }
    } 
}
int query(int l,int r){
    int le=pos[l]+1,ri=pos[r]-1;
    if(le>ri)le=ri=0;
    int res1=f[le][ri],res2=num[le][ri];
    if(pos[l]==pos[r]){
        for(int i=l;i<=r;i++){
            int now=cnt[le][ri][a[i]]+1;
            if(now>res1||(now==res1&&a[i]<res2))res1=now,res2=a[i];
        }
    }else{
        for(int i=l;i<=right[pos[l]];i++){
            int now=cnt[le][ri][a[i]]+1;
            if(now>res1||(now==res1&&a[i]<res2))res1=now,res2=a[i];
        }
        for(int i=left[pos[r]];i<=r;i++){
            int now=cnt[le][ri][a[i]]+1;
            if(now>res1||(now==res1&&a[i]<res2))res1=now,res2=a[i];
        }
    }
    return b[res2];
}
signed main(){
    scanf("%d%d",&n,&m);
    build();
    int las=0;
    while(m--){
        int l,r;
        scanf("%d%d",&l,&r);
        l=(l+las-1)%n+1;
        r=(r+las-1)%n+1;
        if(l>r)swap(l,r);
        printf("%d\n",las=query(l,r)); 
    }
    return 0;
}

by bamboo12345 @ 2022-09-09 14:26:24

@黑影洞人 其实当两个端点在同一个块内的统计并不是cnt[le][ri][a[i]]+1吧


by bamboo12345 @ 2022-09-09 14:28:49

@黑影洞人 query里的每个数次数统计很有问题啊


by 黑影洞人 @ 2022-09-09 14:31:50

@bamboo123 多谢,已经A了


|