题目:P1440 代码1

#include<bits/stdc++.h>
using namespace std;
#define MN 2000010
#define MC 1500
int n,m,a[MN],len,c,st[MC],ed[MC],bl[MN],mi[MC],pmi[MC][MC],nmi[MC][MC];
int rd(){
    int x=0;char c=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9'){
        x=10*x+c-'0';
        c=getchar();
    }
    return x;
}
void init(){
    len=sqrt(n);
    c=(n-1)/len+1;
    for(int i=1;i<=c;i++){
        st[i]=ed[i-1]+1;
        ed[i]=i*len;
        mi[i]=1e8;
    }
    ed[c]=n;
    for(int i=1;i<=c;i++){
        for(int j=st[i];j<=ed[i];j++){
            bl[j]=i;
            mi[i]=min(mi[i],a[j]);
            pmi[i][j-st[i]+1]=mi[i];
        }
        int ccf=1e8;
        for(int j=ed[i];j>=st[i];j--){
            ccf=min(ccf,a[j]);
            nmi[i][j-st[i]+1]=ccf;
        }
    }
}
int ask(int l,int r){
    int ans=1e8,p=bl[l],q=bl[r];
    if(p==q){
        for(int i=l;i<=r;i++)ans=min(ans,a[i]);
    }
    else{
        ans=min(ans,nmi[p][l-st[p]+1]);
        ans=min(ans,pmi[q][r-st[q]+1]);
        for(int i=p+1;i<=q-1;i++)ans=min(ans,mi[i]);
    }
    return ans;
}
int main(){
    n=rd();m=rd();
    for(int i=1;i<=n;i++)a[i]=rd();
    init();
    cout<<"0\n";
    for(int i=2;i<=n;i++){
        cout<<ask(max(i-m,1),i-1)<<"\n";
    }
    return 0;
}

代码2

#include<bits/stdc++.h>
using namespace std;
#define MN 2000010
#define MC 1500
int n,m,a[MN],len,c,st[MC],ed[MC],bl[MN],pmi[MC][MC],nmi[MC][MC],ccf;
int rd(){
    int x=0;char c=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9'){
        x=10*x+c-'0';
        c=getchar();
    }
    return x;
}
void init(){
    len=sqrt(n);
    c=(n-1)/len+1;
    for(int i=1;i<=c;i++){
        st[i]=ed[i-1]+1;
        ed[i]=i*len;
    }
    ed[c]=n;
    for(int i=1;i<=c;i++){
        ccf=1e8;
        for(int j=st[i];j<=ed[i];j++){
            bl[j]=i;
            ccf=min(ccf,a[j]);
            pmi[i][j-st[i]+1]=ccf;
        }
        ccf=1e8;
        for(int j=ed[i];j>=st[i];j--){
            ccf=min(ccf,a[j]);
            nmi[i][j-st[i]+1]=ccf;
        }
    }
}
int ask(int l,int r){
    int ans=1e8,p=bl[l],q=bl[r];
    if(p==q){
        for(int i=l;i<=r;i++)ans=min(ans,a[i]);
    }
    else{
        ans=min(ans,nmi[p][l-st[p]+1]);
        ans=min(ans,pmi[q][r-st[q]+1]);
        for(int i=p+1;i<=q-1;i++)ans=min(ans,pmi[i][ed[i]-st[i]+1]);
    }
    return ans;
}
int main(){
    n=rd();m=rd();
    for(int i=1;i<=n;i++)a[i]=rd();
    init();
    cout<<"0\n";
    for(int i=2;i<=n;i++){
        cout<<ask(max(i-m,1),i-1)<<"\n";
    }
    return 0;
}

为什么，为什么代码2只把代码1保存每个块中的最小值的数组优化掉了（因为有保存每个块的前缀和后缀最小值的数组，可以直接得到每个块中的最小值），可是运行速度反而变慢了不少，导致100pts->80pts，搞不明白这是为什么