题目: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，搞不明白这是为什么