求助分块模版题

P4168 [Violet] 蒲公英

haooo @ 2020-07-22 16:01:15

#include<bits/stdc++.h>
using namespace std;
#define RT register
const int MAXN=40005;
int n,m,t;//n表示长度,m表示询问个数,t表示块数 
int R[205],L[205]; //表示每个块的左边界与右边界 
int a[MAXN];//每个蒲公英的种类,里面存的是hash值 
int fh[MAXN];//反hash数组,存hash值所代表的真实种类 
int pos[MAXN];//每个蒲公英在第几块 
int pre[205][MAXN];//前缀和,pre[i][j]表示前i块,种类j的个数 
int cnt;//种类的总数(有多少种蒲公英) 
unordered_map <int,int> ha;//
inline int read(){//快读 
    int s=0,w=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))s=10*s+ch-'0',ch=getchar();
    return s*w;
}
int h(int x){//离散化,我用的是unordered_map 
    if(ha.count(x)) return ha[x];//已经出现过 
    fh[++cnt]=x;//没有出现过,cnt++ 
    return ha[x]=cnt;//返回hash值 
}
int ask(int l,int r){//询问函数 
    int ans=0;
    int p=pos[l],q=pos[r];//l所在的块与r所在的块 
    if(p==q||p+1==q){//相临,直接暴力
        int vis[MAXN]={};//记录出现次数
        for(RT int i=l;i<=r;i++)    vis[a[i]]++; //暴力从左到右依次扫描
        int maxn=0;//最大值 
        for(RT int i=1;i<=cnt;i++){//暴力比较 
            if(vis[i]>maxn||(fh[i]<fh[ans]&&vis[i]==maxn)){ //如果当前数量大于最大值
            //  或者等于当前最大值种类序号小与当前最大种类序号
                maxn=vis[i];//更改最大值
                ans=i;//更改答案
            }
        }
    }
    else{//相隔大于一块 
    //  cout<<2<<"\n";
        int vis[MAXN]={};//记录出现次数 
        for(RT int i=l;i<=R[p];i++) vis[a[i]]++;//当前种类数目+1
        for(RT int i=L[q];i<=r;i++) vis[a[i]]++;//当前种类数目+1
        for(RT int i=1;i<=cnt;i++)  vis[i]+=pre[q-1][i]-pre[p][i];//暴力每一个种类,加上区间和 
        int maxn=0;//最大值 
        for(RT int i=1;i<=cnt;i++){//爆力扫描一遍 
    //      cout<<fh[i]<<" "<<vis[i]<<"\n";
            if(vis[i]>maxn||(fh[i]<fh[ans]&&vis[i]==maxn)){//如果当前数量大于最大值
                //  或者等于当前最大值种类编号小与当前最大种类编号 
                maxn=vis[i];//更改最大值 
                ans=i;//更改答案 
            }
        }
    }
    return ans;
}
int main(){
    //freopen("P4168.in","r",stdin);
    //freopen("my.out","w",stdout);
    n=read();m=read();//输入n,m 
    int kkk;//一个变量,记录当时输入的原种类编号 
    for(RT int i=1;i<=n;i++){//输入a[i] 
        kkk=read();
        a[i]=h(kkk);//以hash值存入 
    }
    t=sqrt(n);
    for(RT int i=1;i<=t;i++){//处理左边界与右边界 
        L[i]=(i-1)*t+1;
        R[i]=i*t;
    }
    if(R[t]!=n){//右边还有一部分还未入块 
        L[++t]=R[t-1]+1;
        R[t]=n;
    }
    for(RT int i=1;i<=t;i++){//循环每个块 
        for(RT int j=L[i];j<=R[i];j++){//暴力扫描 
            pos[j]=i;//位置 
            for(RT int k=i;k<=t;k++)    pre[k][a[j]]++;//预处理前缀和 
        }
    }
    int x=0;
    fh[0]=40005;//使ans初始的反hash最大 
    while(m--){
        int l,r;
        int lo,ro;
        lo=read();ro=read();//输入 
        l=((lo+x-1)%n)+1;//解密 
        r=((ro+x-1)%n)+1;
        if(l>r) swap(l,r);//交换 
        x=fh[ask(l,r)];//x赋值 
        printf("%d\n",x);//输出 
    }
    return 0;
}

75分

错了前五个点


by 1saunoya @ 2020-07-22 16:07:11

数据结构自己调。。。


by 1saunoya @ 2020-07-22 16:07:24

这种题不会有人来帮你调的.jpg


by haooo @ 2020-07-22 16:32:48


by Remake_ @ 2020-09-24 22:25:20

qndmbt


|