# JZOJ 5417. 【NOIP2017提高A组集训10.24】方阵

xiaoxiao2021-02-28  3

# Sample Input

3 3 1 2 3 4 5 6 7 8 9 3 SUM 0 0 1 1 MAX 0 0 2 2 MIN 0 1 1 1

12 9 2

# Solution

F[i][j][k] (i,j) 向下延伸 2k 、向右延伸 2k 的最大值，最小值同理。

# Code

#include<cstdio> #include<cmath> using namespace std; const int N=801; int a[N][N],sum[N][N],f[N][N][10],g[N][N][10],p[11]; inline int read() { int X=0,w=1; char ch=0; while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();} while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar(); return X*w; } inline int write(int x) { if(x>9) write(x/10); putchar(x+'0'); } inline int max(int x,int y) { return x>y?x:y; } inline int min(int x,int y) { return x<y?x:y; } int main() { int n=read(),m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { f[i][j][0]=g[i][j][0]=a[i][j]=read(); sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]; } for(int i=p[0]=1;i<=10;i++) p[i]=p[i-1]<<1; for(int k=1;k<10;k++) for(int i=1;i<=n && i+p[k]-1<=n;i++) for(int j=1;j<=m && j+p[k]-1<=m;j++) { f[i][j][k]=max(f[i][j][k-1],f[i][j+p[k-1]][k-1]); f[i][j][k]=max(f[i][j][k],max(f[i+p[k-1]][j][k-1],f[i+p[k-1]][j+p[k-1]][k-1])); g[i][j][k]=min(g[i][j][k-1],g[i][j+p[k-1]][k-1]); g[i][j][k]=min(g[i][j][k],min(g[i+p[k-1]][j][k-1],g[i+p[k-1]][j+p[k-1]][k-1])); } int q=read(); while(q--) { char ch=getchar(); while(ch!='X' && ch!='N' && ch!='U') ch=getchar(); int x1=read()+1,y1=read()+1,x2=read()+1,y2=read()+1; if(ch=='U') { write(sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]),putchar('\n'); continue; } int ans=ch=='N'?3000:0,z=min(log2(x2-x1+1),log2(y2-y1+1)); if(ch=='X') { for(int yy=y1;yy+p[z]<=y2;yy+=p[z]) ans=max(ans,max(f[x1][yy][z],f[x2-p[z]+1][yy][z])); for(int xx=x1;xx+p[z]<=x2;xx+=p[z]) ans=max(ans,max(f[xx][y1][z],f[xx][y2-p[z]+1][z])); ans=max(ans,max(f[x1][y1][z],f[x1][y2-p[z]+1][z])); ans=max(ans,max(f[x2-p[z]+1][y1][z],f[x2-p[z]+1][y2-p[z]+1][z])); }else { for(int yy=y1;yy+p[z]<=y2;yy+=p[z]) ans=min(ans,min(g[x1][yy][z],g[x2-p[z]+1][yy][z])); for(int xx=x1;xx+p[z]<=x2;xx+=p[z]) ans=min(ans,min(g[xx][y1][z],g[xx][y2-p[z]+1][z])); ans=min(ans,min(g[x1][y1][z],g[x1][y2-p[z]+1][z])); ans=min(ans,min(g[x2-p[z]+1][y1][z],g[x2-p[z]+1][y2-p[z]+1][z])); } write(ans),putchar('\n'); } return 0; }