https://www.luogu.org/PRoblem/show?pid=2216 一開始我想了個前墜和，后來發現有bug； 過了一個月發現是二維線段樹水題，但好像二維線段樹太麻煩； 然后看了題解； 1.二維倍增RMQ 2.單調隊列*2； 那我都打一打把；
二維倍增RMQ ma[i][j][k]表示 i,j~i+(1<< k)-1, j+(1<< k)-1) 的最大值 然后直接無腦RMQ； 注意一下區間邊界要不要+1要不要-1； 這種問題模擬即可
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#define Ll long longusing namespace std;int ma[1001][1001][11],mi[1001][1001][10];int n,m,q,x,y,z,ans;int RMQ(int x,int y,int xx,int yy){ return max(max(ma[x][y][z],ma[xx-(1<<z)+1][yy-(1<<z)+1][z]),max(ma[x][yy-(1<<z)+1][z],ma[xx-(1<<z)+1][y][z]))- min(min(mi[x][y][z],mi[xx-(1<<z)+1][yy-(1<<z)+1][z]),min(mi[x][yy-(1<<z)+1][z],mi[xx-(1<<z)+1][y][z]));}int main(){ scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ scanf("%d",&x); ma[i][j][0]=mi[i][j][0]=x; } for(int k=1;(1<<k)<=min(n,m);k++) for(int i=1;i<=n-(1<<k)+1;i++) for(int j=1;j<=m-(1<<k)+1;j++){ ma[i][j][k]=max(max(ma[i][j][k-1],ma[i+(1<<(k-1))][j+(1<<(k-1))][k-1]), max(ma[i][j+(1<<(k-1))][k-1],ma[i+(1<<(k-1))][j][k-1])); mi[i][j][k]=min(min(mi[i][j][k-1],mi[i+(1<<(k-1))][j+(1<<(k-1))][k-1]), min(mi[i][j+(1<<(k-1))][k-1],mi[i+(1<<(k-1))][j][k-1])); } ans=1e9; z=0; while((1<<(z+1))<q)z++; for(int i=1;i<=n-q+1;i++) for(int j=1;j<=m-q+1;j++)ans=min(ans,RMQ(i,j,i+q-1,j+q-1)); printf("%d",ans);}單調隊列*2 本來以為很水，然后打了40分種； 錯誤1是+1-1搞錯了，檢查了好半天； 所以關于區間邊界的這種一定要預先算好； 然后是復制優先隊列時數組搞錯了； …. 當然的，時空復雜度，單調隊列明顯優于RMQ
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#define Ll long longusing namespace std;int a[1001][1001],mi[1001][1001],ma[1001][1001],q[1001];int n,m,p,l,r,ans;int main(){ scanf("%d%d%d",&n,&m,&p); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)scanf("%d",&a[i][j]); for(int i=1;i<=n;i++){ l=1;r=0;q[0]=0;a[i][0]=1e9+1; for(int j=1;j<p;j++){ while(r>=l&&a[i][q[r]]<=a[i][j])r--; q[++r]=j; } for(int j=p;j<=m;j++){ while(r>=l&&a[i][q[r]]<=a[i][j])r--; q[++r]=j; while(q[l]+p-1<j)l++; ma[i][j-p+1]=a[i][q[l]]; } l=1;r=0;q[0]=0;a[i][0]=-1e9; for(int j=1;j<p;j++){ while(r>=l&&a[i][q[r]]>=a[i][j])r--; q[++r]=j; } for(int j=p;j<=m;j++){ while(r>=l&&a[i][q[r]]>=a[i][j])r--; q[++r]=j; while(q[l]+p-1<j)l++; mi[i][j-p+1]=a[i][q[l]]; } } for(int j=1;j<=m-p+1;j++){ l=1;r=0;q[0]=0;a[0][j]=1e9+1; for(int i=1;i<p;i++){ while(r>=l&&ma[q[r]][j]<=ma[i][j])r--; q[++r]=i; } for(int i=p;i<=n;i++){ while(r>=l&&ma[q[r]][j]<=ma[i][j])r--; q[++r]=i; while(q[l]+p-1<i)l++; ; ma[i-p+1][j]=ma[q[l]][j]; } l=1;r=0;q[0]=0;a[0][j]=-1e9; for(int i=1;i<p;i++){ while(r>=l&&mi[q[r]][j]>=mi[i][j])r--; q[++r]=i; } for(int i=p;i<=n;i++){ while(r>=l&&mi[q[r]][j]>=mi[i][j])r--; q[++r]=i; while(q[l]+p-1<i)l++; mi[i-p+1][j]=mi[q[l]][j]; } }// cout<<endl;for(int i=1;i<=n;i++){// for(int j=1;j<=m;j++)cout<<ma[i][j]<<' ';cout<<endl;} ans=1e9; for(int i=1;i<=n-p+1;i++) for(int j=1;j<=m-p+1;j++)ans=min(ans,ma[i][j]-mi[i][j]); printf("%d",ans);}新聞熱點
疑難解答
