考试yy二维ST表失败导致爆零。
其实和一维的ST表很像...
也是设$f[i][j][p][q]$为以$(i, j)$为左上角，长为$2^p$，宽为$2^q$的矩形的最大值。
算法流程是先把每一行都分别求一遍一维的ST表，然后再把行与行之间合并...
查询和一维ST表类似
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define reg register inline int read() { int res=0;char ch=getchar();bool fu=0; while(!isdigit(ch))fu|=(ch=='-'),ch=getchar(); while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar(); return fu?-res:res; } int n, m; int a[305][305]; int st[505][505][10][10]; inline int query(int x1, int y1, int x2, int y2) { int k1 = log2(x2 - x1 + 1), k2 = log2(y2 - y1 + 1); return max(st[x1][y1][k1][k2], max(st[x2-(1<<k1)+1][y1][k1][k2], max(st[x1][y2-(1<<k2)+1][k1][k2], st[x2-(1<<k1)+1][y2-(1<<k2)+1][k1][k2]))); } int main() { freopen("yy.in", "r", stdin); freopen("yy.out", "w", stdout); n = read(), m = read(); for (reg int i = 1 ; i <= n ; ++i) for (reg int j = 1 ; j <= m ; ++j) st[i][j][0][0] = a[i][j] = read(); for (reg int p = 0 ; p <= 9 ; p ++) for (reg int q = 0 ; q <= 9 ; q ++) if (p != 0 or q != 0) for (reg int i = 1 ; i + (1<<p) - 1 <= n ; i ++) for (reg int j = 1 ; j + (1<<q) - 1 <= m ; j ++) if (!p) st[i][j][p][q] = max(st[i][j][p][q - 1], st[i][j+(1<<(q-1))][p][q - 1]); else st[i][j][p][q] = max(st[i][j][p-1][q], st[i+(1<<(p-1))][j][p-1][q]); int q = read(); while(q--) { int x1=read(),y1=read(),x2=read(),y2=read(); printf("%d ", query(x1,y1,x2,y2)); } return 0; }