1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112
| #include <cstdio> #include <cmath> #define maxN 1010 #define maxM 1010 int g[11][11][maxN][maxM], f[maxN][maxM], a[maxN][maxM]; int read () { char c = getchar(); while(c < '0' || c > '9') { c = getchar(); } int x = 0; while(c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); } return x; } int min (int x, int y) { return x < y ? x : y; } int max (int x, int y) { return x > y ? x : y; } int query (int xa, int ya, int xb, int yb) { int p = (int)log2(xb - xa + 1), q = (int)log2(yb - ya + 1); int ans = max(g[p][q][xa][ya], g[p][q][xb - (1 << p) + 1][ya]); ans = max(ans, max(g[p][q][xa][yb - (1 << q) + 1], g[p][q][xb - (1 << p) + 1][yb - (1 << q) + 1])); return ans; } int main () { int n = 0, m = 0; scanf("%d %d", &n, &m); 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++) { for(int j = 1;j <= m; j++) { f[i][j] = a[i][j] * (min(f[i][j - 1], min(f[i - 1][j - 1], f[i - 1][j])) + 1); } } for(int i = 1;i <= n; i++) { for(int j = 1;j <= m; j++) { g[0][0][i][j] = f[i][j]; } } int N = (int)log2(n) + 1, M = (int)log2(m) + 1; for(int k = 0;k <= N; k++) { for(int l = 0;l <= M; l++) { if(!k && !l) { continue; } for(int i = 1;i <= n - (1 << k) + 1; i++) { for(int j = 1;j <= m - (1 << l) + 1; j++) { if(k) { g[k][l][i][j] = max(g[k - 1][l][i][j], g[k - 1][l][i + (1 << (k - 1))][j]); } else { g[k][l][i][j] = max(g[k][l - 1][i][j], g[k][l - 1][i][j + (1 << (l - 1))]); } } } } } int T = 0; scanf("%d", &T); int L = 0, R = min(n, m); while(T--) { int xa = 0, ya = 0, xb = 0, yb = 0; xa = read(); ya = read(); xb = read(); yb = read(); int l = L, r = min(R, min(xb - xa + 1, yb - ya + 1)); while(l < r) { int mid = (l + r + 1) / 2; if(query(xa + mid - 1, ya + mid - 1, xb, yb) >= mid) { l = mid; } else { r = mid - 1; } } printf("%d\n", l); } return 0; }
|