题意很简单 就不说了
为了把它推广成矩形的
写了这种查询是O(n)的方法
当然还有O(1)的矩形的方法了 只不过太麻烦了
但是对于正方形来讲 还是比较好弄的
#include <iostream> #include <algorithm> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <queue> #include <vector> #include <map> #include <set> #include <stack> #define eps 1e-5 #define MAXN 255 #define MAXM 111111 #define INF 1000000000 using namespace std; int mx[MAXN][MAXN][8], mi[MAXN][MAXN][8]; int n, b, q, a, c; void rmqinit() { int l = int(log(double(n)) / log(2.0)) ; for(int k = 1; k <= n ; k++) for(int j = 1; j <= l; j++) for(int i = 1; i + (1 << (j - 1))- 1 <= n; i++) { mx[k][i][j] = max(mx[k][i][j - 1], mx[k][i + (1 << (j - 1 ))][j - 1]) ; mi[k][i][j] = min(mi[k][i][j - 1], mi[k][i + (1 << (j - 1 ))][j - 1]) ; } } int rmqmax(int lx, int ly, int rx, int ry) // lx, ly为左上角的点 rx ry为右下角的点 { int l = int(log(double(ry - ly + 1)) / log(2.0)); int ret = -1; for(int k = lx; k <= rx ; k++) ret = max(ret, max(mx[k][ly][l], mx[k][ry - (1 << l) + 1][l])); return ret; } int rmqmin(int lx, int ly, int rx, int ry) // lx, ly为左上角的点 rx ry为右下角的点 { int l = int(log(double(ry - ly + 1)) / log(2.0)); int ret = INF; for(int k = lx; k <= rx ; k++) ret = min(ret, min(mi[k][ly][l], mi[k][ry - (1 << l) + 1][l])); return ret; } int main() { while(scanf("%d%d%d", &n, &b, &q) != EOF) { for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { scanf("%d",&a); mx[i][j][0] = mi[i][j][0] = a ; } rmqinit(); while(q--) { scanf("%d%d", &a, &c) ; int rx = a + b - 1; if(rx > n) rx = n; int ry = c + b - 1; if(ry > n) ry = n; printf("%d\n", rmqmax(a, c, rx, ry) - rmqmin(a, c, rx, ry)) ; } } return 0; }
查询是O(1)的那种 仅限于正方形
#include <iostream> #include <algorithm> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <queue> #include <vector> #include <map> #include <set> #include <stack> #define eps 1e-5 #define MAXN 255 #define MAXM 111111 #define INF 1000000000 using namespace std; int mx[MAXN][MAXN][8], mi[MAXN][MAXN][8]; int n, b, q; int Get_mx(int x, int y, int p) { int ret = -INF; ret = max(ret, mx[x][y][p]); if (x + (1 << p) <= n) ret = max(ret, mx[x + (1 << p)][y][p]); if (y + (1 << p) <= n) ret = max(ret, mx[x][y + (1 << p)][p]); if ((x + (1 << p) <= n) && (y + (1 << p) <= n)) ret = max(ret, mx[x + (1 << p)][y + (1 << p)][p]); return ret; } int Get_mi(int x, int y, int p) { int ret = INF; ret = min(ret, mi[x][y][p]); if (x + (1 << p) <= n) ret = min(ret, mi[x + (1 << p)][y][p]); if (y + (1 << p) <= n) ret = min(ret, mi[x][y + (1 << p)][p]); if ((x + (1 << p) <= n) && (y + (1 << p) <= n)) ret = min(ret, mi[x + (1 << p)][y + (1 << p)][p]); return ret; } void rmqinit() { int l = int(log(n * 1.0) / log(2.0)); for (int i = 1; i <= l; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++) { mx[j][k][i] = Get_mx(j, k, i - 1); mi[j][k][i] = Get_mi(j, k, i - 1); } } int rmqmax(int x, int y, int b) { int p = int(log(b * 1.0) / log(2.0)); int ret = -INF; ret = max(ret, mx[x][y][p]); if (x + b - (1 << p) <= n) ret = max(ret, mx[x + b - (1 << p)][y][p]); if (y + b - (1 << p) <= n) ret = max(ret, mx[x][y + b - (1 << p)][p]); if ((x + b - (1 << p) <= n) && (y + b - (1 << p) <= n)) ret = max(ret, mx[x + b - (1 << p)][y + b - (1 << p)][p]); return ret; } int rmqmin(int x, int y, int b) { int p = int(log(b * 1.0) / log(2.0)); int ret = INF; ret = min(ret, mi[x][y][p]); if (x + b - (1 << p) <= n) ret = min(ret, mi[x + b - (1 << p)][y][p]); if (y + b - (1 << p) <= n) ret = min(ret, mi[x][y + b - (1 << p)][p]); if ((x + b - (1 << p) <= n) && (y + b - (1 << p) <= n)) ret = min(ret, mi[x + b - (1 << p)][y + b - (1 << p)][p]); return ret; } int main() { int val; scanf("%d%d%d", &n, &b, &q); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { scanf("%d", &val); mx[i][j][0] = mi[i][j][0] = val; } rmqinit(); int x, y; while(q--) { scanf("%d%d", &x, &y); printf("%d\n", rmqmax(x, y, b) - rmqmin(x, y, b)); } return 0; }
然后就是推广到矩形的写法 比较麻烦 占用的内存也比较大
#include <iostream> #include <algorithm> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <queue> #include <vector> #include <map> #include <set> #include <stack> #define eps 1e-5 #define MAXN 255 #define MAXM 111111 #define INF 1000000000 using namespace std; int n, b, k, m; int mi[MAXN][MAXN][10][10]; int mx[MAXN][MAXN][10][10]; int val[MAXN][MAXN]; void init() { for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) mi[i][j][0][0] = mx[i][j][0][0] = val[i][j]; int kn = (int)(log((double)n) / log(2.0)); int km = (int)(log((double)m) / log(2.0)); for(int i = 0; i <= kn; ++i) for(int j = 0; j <= km; ++j) { if (!i && !j) continue; for(int r = 1; r + (1 << i) - 1 <= n; r++) for(int c = 1; c + (1 << j) - 1 <= m; c++) { if (!i) { mi[r][c][i][j] = min(mi[r][c][i][j - 1], mi[r][c + (1 << (j - 1))][i][j - 1]); mx[r][c][i][j] = max(mx[r][c][i][j - 1], mx[r][c + (1 << (j - 1))][i][j - 1]); } else { mi[r][c][i][j] = min(mi[r][c][i - 1][j], mi[r + (1 << (i - 1))][c][i - 1][j]); mx[r][c][i][j] = max(mx[r][c][i - 1][j], mx[r + (1 << (i - 1))][c][i - 1][j]); } } } } int rmqmax(int r1, int c1, int r2, int c2) { int kr = (int)(log((double)r2 - r1 + 1) / log(2.0)); int kc = (int)(log((double)c2 - c1 + 1) / log(2.0)); int t1 = mx[r1][c1][kr][kc]; int t2 = mx[r2 - (1 << kr) + 1][c1][kr][kc]; int t3 = mx[r1][c2 - (1 << kc) + 1][kr][kc]; int t4 = mx[r2 - (1 << kr) + 1][c2 - (1 << kc) + 1][kr][kc]; return max(max(t1, t2), max(t3, t4)); } int rmqmin(int r1, int c1, int r2, int c2) { int kr = (int)(log((double)r2 - r1 + 1) / log(2.0)); int kc = (int)(log((double)c2 - c1 + 1) / log(2.0)); int m1 = mi[r1][c1][kr][kc]; int m2 = mi[r2 - (1 << kr)+1][c1][kr][kc]; int m3 = mi[r1][c2 - (1 << kc) + 1][kr][kc]; int m4 = mi[r2 - (1 << kr) + 1][c2 - (1 << kc) + 1][kr][kc]; return min(min(m1, m2), min(m3, m4)); } int main() { scanf("%d%d%d", &n, &m, &k); for(int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d", &val[i][j]); init(); int r1, c1, r2, c2; for (int i = 0; i < k; ++i) { scanf("%d%d%d%d", &r1, &c1, &r2, &c2); printf("%d\n", rmqmax(r1, c1, r2, c2)); } return 0; }