POJ 2019 二维RMQ

题意很简单 就不说了

为了把它推广成矩形的

写了这种查询是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;
}