RMQ-洛谷P2216 [HAOI2007] 理想的正方形

2019-11-08 01:42:13

字体：大中小

来源：转载

供稿：网友

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);}

上一篇：6.4.3树和森林的遍历

下一篇：HDU 1087 Super Jumping! Jumping! Jumping! (基础dp)