学习分块吸入臭氧求助

P4168 [Violet] 蒲公英

Rye_Catcher @ 2018-06-23 22:38:26

rt,debug了好久,开O2上去3个点Too Many Or Too Few Lines,一片RE,求助

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <map>
#include <vector>
#include <queue>
#include <unordered_map>  
#define ll long long 
#define ri  int 
using namespace std;
const int inf=0x7fffffff;
const int maxn=40005;
const int maxx=505;
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while(!isdigit(c=getchar()))ne=c=='-';
    x=c-48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
    x=ne?-x:x;
    return ;
}
int n,m,size;
int pos[maxx],L[maxx],R[maxx],f[maxx][maxx],cnt[maxx],fun[maxn];
unordered_map <int,int>rec;//离散化
vector <int>loc[maxn];//记录各数出现位置 
int a[maxn],tot=0;
inline void pre(int now){
    int mx=-1,ans=0;
    memset(cnt,0,sizeof(cnt));
    for(ri i=L[now];i<=n;i++){
        cnt[a[i]]++;
        if(cnt[a[i]]>mx||(cnt[a[i]]==mx&&fun[a[i]]<fun[ans])){/*有若干种蒲公英出现次数相同,则输出种类编号最小的那个。*/
            mx=cnt[a[i]];
            ans=a[i];
        }
        f[now][pos[i]]=ans;
        //cout<<pos[i]<<' '<<ans<<endl;
    }
    return ;
}
inline int get(int l,int r,int x){
    return upper_bound(loc[x].begin(),loc[x].end(),r)-lower_bound(loc[x].begin(),loc[x].end(),l);
}
inline int query(int l,int r){
    int ans=f[pos[l]+1][pos[r]-1],tmp;
    int mx=get(l,r,ans),p=pos[l],q=pos[r];
    if(p!=q){
        for(ri i=l;i<=R[p];i++){
            tmp=get(l,r,a[i]);
            if(tmp>mx||(tmp==mx&&fun[a[i]]<fun[ans])){
                mx=tmp,ans=a[i];
            }
        }
        for(ri i=L[q];i<=r;i++){
            tmp=get(l,r,a[i]);
            if(tmp>mx||(tmp==mx&&fun[a[i]]<fun[ans])){
                mx=tmp,ans=a[i];
            }
        }
    }
    else{
        for(ri i=l;i<=r;i++){
            tmp=get(l,r,a[i]);
            if(tmp>mx||(tmp==mx&&fun[a[i]]<fun[ans])){
                mx=tmp,ans=a[i];
            }
        }
    }
    return ans;
}
int main(){
    read(n),read(m);
    size=sqrt(n);
    for(ri i=1;i<=n;i++){
        read(a[i]);
        if(rec[a[i]]==0){
            rec[a[i]]=++tot;
            fun[tot]=a[i];
        }
        a[i]=rec[a[i]];
        loc[a[i]].push_back(i);
    }
    for(ri i=1;i<=size;i++){
        L[i]=(i-1)*size+1;
        R[i]=i*size;
    }
    if(R[size]<n){size++,L[size]=R[size-1]+1,R[size]=n;}
    for(ri i=1;i<=size;i++){
        for(ri j=L[i];j<=R[i];j++){
            pos[j]=i;
        }
    }
    for(ri i=1;i<=size;i++)pre(i);
    int x=0,l,r,c;
    while(m--){
        read(l),read(r);  
        l=(l+x-1)%n+1,r=(r+x-1)%n+1;
        if(l>r)swap(l,r);
        x=fun[query(l,r)];
        printf("%d\n",x);
    }
    return 0;
}

by 小粉兔 @ 2018-06-24 00:02:13

好强啊……我分块都没做这题


by Mudrobøt @ 2018-08-07 17:50:33

@Rye_Catcher 吸纯净臭氧!


by Delva @ 2018-08-07 17:50:33

@Rye_Catcher 吸纯净臭氧啊


|