题面 假的数据。。。考场上被坑成0分。 首先两个log的二维ST表很好想，st[i][j][k][l]表示以点（i，j）向右2^k，向下2^l的矩形内的答案。 （假设）考虑真的长不超过宽的两倍，我们可以把它分成两个以宽为边长的正方形（当然可能会有部分重叠），那么询问都转化成正方形，只需要预处理st[i][j][k]表示以点（i，j）向右下2^k的正方形内的答案。时间和空间都少了一个log。 原版代码：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #define chkmin(a,b) a=min(a,b) #define chkmax(a,b) a=max(a,b) using namespace std; int n,m,w,q,a[810][810],mx[810][810][11],mi[810][810][11]; long long sum[810][810]; int qmx(int x1,int y1,int x2,int y2,int k) { int t=(int)(log(k)/log(2)),r=(1<<t); return max(max(mx[x1][y1][t],mx[x2-r+1][y2-r+1][t]),max(mx[x2-r+1][y1][t],mx[x1][y2-r+1][t])); } int qmi(int x1,int y1,int x2,int y2,int k) { int t=(int)(log(k)/log(2)),r=(1<<t); return min(min(mi[x1][y1][t],mi[x2-r+1][y2-r+1][t]),min(mi[x2-r+1][y1][t],mi[x1][y2-r+1][t])); } int main() { freopen("phalanx.in","r",stdin); freopen("phalanx.out","w",stdout); scanf("%d%d",&n,&m); w=min(n,m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); memset(mi,0x3f,sizeof(mi)); memset(mx,0,sizeof(mx)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]; mx[i][j][0]=mi[i][j][0]=a[i][j]; } for(int k=1;(1<<k)<=w;k++) for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { mx[i][j][k]=mx[i][j][k-1]; if(i+(1<<(k-1))<=n) chkmax(mx[i][j][k],mx[i+(1<<(k-1))][j][k-1]); if(j+(1<<(k-1))<=m) chkmax(mx[i][j][k],mx[i][j+(1<<(k-1))][k-1]); if(i+(1<<(k-1))<=n&&j+(1<<(k-1))<=m) chkmax(mx[i][j][k],mx[i+(1<<(k-1))][j+(1<<(k-1))][k-1]); } for(int k=1;(1<<k)<=w;k++) for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { mi[i][j][k]=mi[i][j][k-1]; if(i+(1<<(k-1))<=n) chkmin(mi[i][j][k],mi[i+(1<<(k-1))][j][k-1]); if(j+(1<<(k-1))<=m) chkmin(mi[i][j][k],mi[i][j+(1<<(k-1))][k-1]); if(i+(1<<(k-1))<=n&&j+(1<<(k-1))<=m) chkmin(mi[i][j][k],mi[i+(1<<(k-1))][j+(1<<(k-1))][k-1]); } scanf("%d",&q); for(int i=1;i<=q;i++) { char opt[3]; int x1,y1,x2,y2,k; scanf("%s",opt); scanf("%d%d%d%d",&x1,&y1,&x2,&y2);x1++;y1++;x2++;y2++; k=min(x2-x1,y2-y1); if(opt[1]=='U') {printf("%lld\n",sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]);continue;} if(opt[1]=='A') {printf("%d\n",max(qmx(x1,y1,x1+k,y1+k,k+1),qmx(x2-k,y2-k,x2,y2,k+1)));} if(opt[1]=='I') {printf("%d\n",min(qmi(x1,y1,x1+k,y1+k,k+1),qmi(x2-k,y2-k,x2,y2,k+1)));} } return 0; }但因为数据的原因，要把它分成多个正方形，于是写一个循环来分。 循环版代码：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #define chkmin(a,b) a=min(a,b) #define chkmax(a,b) a=max(a,b) using namespace std; int n,m,w,q,a[810][810],mx[810][810][11],mi[810][810][11]; long long sum[810][810]; int qmx(int x1,int y1,int x2,int y2,int k) { int t=(int)(log(k)/log(2)),r=(1<<t); return max(max(mx[x1][y1][t],mx[x2-r+1][y2-r+1][t]),max(mx[x2-r+1][y1][t],mx[x1][y2-r+1][t])); } int qmi(int x1,int y1,int x2,int y2,int k) { int t=(int)(log(k)/log(2)),r=(1<<t); return min(min(mi[x1][y1][t],mi[x2-r+1][y2-r+1][t]),min(mi[x2-r+1][y1][t],mi[x1][y2-r+1][t])); } int spmx(int x1,int y1,int x2,int y2,int k) { int re=0; if(x1+k==x2) { for(int t=1;y1+k<y2;t++,y1+=k+1) chkmax(re,qmx(x1,y1,x2,y1+k,k+1)); chkmax(re,qmx(x1,y2-k,x2,y2,k+1)); } else { for(int t=1;x1+k<x2;t++,x1+=k+1) chkmax(re,qmx(x1,y1,x1+k,y2,k+1)); chkmax(re,qmx(x2-k,y1,x2,y2,k+1)); } return re; } int spmi(int x1,int y1,int x2,int y2,int k) { int re=1e9; if(x1+k==x2) { for(int t=1;y1+k<y2;t++,y1+=k+1) chkmin(re,qmi(x1,y1,x2,y1+k,k+1)); chkmin(re,qmi(x1,y2-k,x2,y2,k+1)); } else { for(int t=1;x1+k<x2;t++,x1+=k+1) chkmin(re,qmi(x1,y1,x1+k,y2,k+1)); chkmin(re,qmi(x2-k,y1,x2,y2,k+1)); } return re; } int main() { freopen("phalanx.in","r",stdin); freopen("phalanx.out","w",stdout); scanf("%d%d",&n,&m); w=min(n,m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); memset(mi,0x3f,sizeof(mi)); memset(mx,0,sizeof(mx)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]; mx[i][j][0]=mi[i][j][0]=a[i][j]; } for(int k=1;(1<<k)<=w;k++) for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { mx[i][j][k]=mx[i][j][k-1]; if(i+(1<<(k-1))<=n) chkmax(mx[i][j][k],mx[i+(1<<(k-1))][j][k-1]); if(j+(1<<(k-1))<=m) chkmax(mx[i][j][k],mx[i][j+(1<<(k-1))][k-1]); if(i+(1<<(k-1))<=n&&j+(1<<(k-1))<=m) chkmax(mx[i][j][k],mx[i+(1<<(k-1))][j+(1<<(k-1))][k-1]); } for(int k=1;(1<<k)<=w;k++) for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { mi[i][j][k]=mi[i][j][k-1]; if(i+(1<<(k-1))<=n) chkmin(mi[i][j][k],mi[i+(1<<(k-1))][j][k-1]); if(j+(1<<(k-1))<=m) chkmin(mi[i][j][k],mi[i][j+(1<<(k-1))][k-1]); if(i+(1<<(k-1))<=n&&j+(1<<(k-1))<=m) chkmin(mi[i][j][k],mi[i+(1<<(k-1))][j+(1<<(k-1))][k-1]); } scanf("%d",&q); for(int i=1;i<=q;i++) { char opt[3]; int x1,y1,x2,y2,k; scanf("%s",opt); scanf("%d%d%d%d",&x1,&y1,&x2,&y2);x1++;y1++;x2++;y2++; k=min(x2-x1,y2-y1); if(opt[1]=='U') {printf("%lld\n",sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]);continue;} if(opt[1]=='A') {printf("%d\n",spmx(x1,y1,x2,y2,k));} if(opt[1]=='I') {printf("%d\n",spmi(x1,y1,x2,y2,k));} } return 0; }