调到人傻了,玄关求调(有注释)

P4168 [Violet] 蒲公英

wujingfey @ 2023-10-17 17:01:06

神奇程序,目前调出来的问题是:手写的对拍都能过,但只有 10pts,下下来数据发现前几行都对,然后开始出错。如果把前几行删了,那么原本出错的查询就正确了。初步认定是查询函数初始化有问题。但我查询函数里的变量都是新定义的并且有初始值

#include<bits/stdc++.h>
using namespace std;
const int N=4e4+5,M=2e2+2,INF=1e9+10;
int n,m,a[N],b[N],c[N],ctop,maxn;
int tong[M][N],x;//tong[i][j]表示j元素到i块的前缀和 
int st[M],ed[M],block,t,pos[N];
int maxx[M][M],maxxx[M][M];//记录块i-j间的出现次数最多的数出现了多少次,以及哪个数出现次数最多 
int query(int l,int r){
    int p=pos[l],q=pos[r];
    int ans1=0,ans2=INF;//ans1最大出现次数,ans2记录是哪个数 
    int t[N]={0};//记录ai出现次数
    if(p==q){//暴力查询区间内 
        for(int i=l;i<=r;i++) 
            t[a[i]]++;
        for(int i=l;i<=r;i++){
            if(t[a[i]]>ans1){
                ans1=t[a[i]];
                ans2=a[i];
            }else if(t[a[i]]==ans1){//相等的时候更新更小的ai 
                ans2=min(ans2,a[i]);
            }
        }
        return ans2;
    }else{
        ans1=maxx[p+1][q-1],ans2=maxxx[p+1][q-1];
        (ans2==0)?ans2=INF:ans2;
        for(int i=l;i<=ed[p];i++){
            int times=tong[q-1][a[i]]-tong[p][a[i]];
            if(t[a[i]]==0) t[a[i]]=times+1;
            else t[a[i]]++;
        }
        for(int i=st[q];i<=r;i++){
            int times=tong[q-1][a[i]]-tong[p][a[i]];
            if(t[a[i]]==0) t[a[i]]=times+1;
            else t[a[i]]++;
        }
        for(int i=l;i<=ed[p];i++){
            if(t[a[i]]>ans1){
                ans1=t[a[i]];
                ans2=a[i];
            }else if(t[a[i]]==ans1){//相等的时候更新更小的ai 
                ans2=min(ans2,a[i]);
            }
        }
        for(int i=st[q];i<=r;i++){
            if(t[a[i]]>ans1){
                ans1=t[a[i]];
                ans2=a[i];
            }else if(t[a[i]]==ans1){//相等的时候更新更小的ai 
                ans2=min(ans2,a[i]);
            }
        }
        return ans2;
    }
}
signed main(){
//  freopen("P4168_1.in","r",stdin);
//  freopen("t1.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    /*------------离散化--------------*/
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++)
        if(b[i-1]!=b[i]||i==1)
            c[++ctop]=b[i];
    for(int i=1;i<=n;i++){
        int www=lower_bound(c+1,c+ctop+1,a[i])-c;
        a[i]=www;
    }
    /*-------------分块---------------*/
    block=sqrt(n);
    t=n/block;
    if(n%block) t++;
    for(int i=1;i<=t;i++){
        st[i]=(i-1)*block+1;
        ed[i]=i*block;
    }
    ed[t]=n;
    for(int i=1;i<=t;i++)
        for(int j=st[i];j<=ed[i];j++)
            pos[j]=i;
    /*--------------预处理前缀和、桶----------------*/
    for(int i=1;i<=n;i++){
        int p=pos[i];
        tong[p][a[i]]++;
    }
    for(int i=1;i<=N-4;i++)
        for(int j=1;j<=t;j++)
            tong[j][i]=tong[j-1][i]+tong[j][i];
    for(int i=1;i<=t;i++){//起点块 
        for(int j=i;j<=t;j++){//终点块
            int res=0,num=INF;
            for(int k=st[j];k<=ed[j];k++){//终点块每个元素 
                if(tong[j][a[k]]-tong[i-1][a[k]]>res){
                    res=tong[j][a[k]]-tong[i-1][a[k]];
                    num=a[k];
                }else if(tong[j][a[k]]-tong[i-1][a[k]]==res){
                    num=min(num,a[k]);
                }
            }
            maxx[i][j]=res,maxxx[i][j]=num;
        }
    }
    /*-------------处理查询----------------*/
    while(m--){
        int l=0,r=0;
        cin>>l>>r;
        l=(l+x-1)%n+1,r=(r+x-1)%n+1;//解压密码   
        if(l>r) swap(l,r);
        x=c[query(l,r)];
        cout<<x<<"\n";
    }
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

by wujingfey @ 2023-10-17 17:03:38

写了个暴力上去,正确性有保正。因为暴力直接复制的读入、离散化、输出,所以这些没毛病。并且 query 的 p==q 验证过无误


by lovely_hyzhuo @ 2023-10-17 17:08:28

我之前也是10pts,咋改的忘了。

你稍等


by wujingfey @ 2023-10-17 17:13:53

又拍了半天,发现不是初始化的问题,因为出现了第一行就错的情况


|