Cornfields POJ

就是求子矩阵中最大值与最小值的差。。。

板子都套不对的人。。。。

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rep(i, a, n) for(int i=a, i<n; i++)
#define lap(i, a, n) for(int i=n; i>=a; i--)
#define lep(i, a, n) for(int i=n; i>a; i--)
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _  ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = 255, INF = 0x7fffffff;
int dp[maxn][maxn][8][8], num[maxn][maxn];
int d[maxn][maxn][8][8];

int rmq(int x1, int y1, int x2, int y2)
{
    int kx = 0, ky = 0;
    while ((1 << (1 + kx)) <= x2 - x1 + 1) kx++;
    while ((1 << (1 + ky)) <= y2 - y1 + 1) ky++;
    int m1 = dp[x1][y1][kx][ky];
    int m2 = dp[x2 - (1 << kx) + 1][y1][kx][ky];
    int m3 = dp[x1][y2 - (1 << ky) + 1][kx][ky];
    int m4 = dp[x2 - (1 << kx) + 1][y2 - (1 << ky) + 1][kx][ky];
    int m5 = max(max(m1, m2), max(m3, m4));

    int n1 = d[x1][y1][kx][ky];
    int n2 = d[x2 - (1 << kx) + 1][y1][kx][ky];
    int n3 = d[x1][y2 - (1 << ky) + 1][kx][ky];
    int n4 = d[x2 - (1 << kx) + 1][y2 - (1 << ky) + 1][kx][ky];
    int n5 = min(min(n1, n2), min(n3, n4));


    return m5 - n5;
}


int main()
{
    int n, b, k;
    while(~scanf("%d%d%d", &n, &b, &k))
    {
        rap(i, 1, n)
            rap(j, 1, n)
            {
                scanf("%d", &num[i][j]);
                dp[i][j][0][0] = d[i][j][0][0] = num[i][j];
            }

        for (int i = 0; (1 << i) <= n; i++) {
            for (int j = 0; (1 << j) <= n; j++) {
                if (i == 0 && j == 0) continue;
                for (int row = 1; row + (1 << i) - 1 <= n; row++)
                    for (int col = 1; col + (1 << j) - 1 <= n; col++) {
                        //当x或y等于0的时候，就相当于一维的RMQ了
                        //if(i == 0) dp[row][col][i][j] = max(dp[row][col][i][j - 1], dp[row][col + (1 << (j - 1))][i][j - 1]);
                        if (j == 0)
                        {
                            dp[row][col][i][j] = max(dp[row][col][i - 1][j], dp[row + (1 << (i - 1))][col][i - 1][j]);
                            d[row][col][i][j] = min(d[row][col][i - 1][j], d[row + (1 << (i - 1))][col][i - 1][j]);
                        }
                        else
                        {
                            dp[row][col][i][j] = max(dp[row][col][i][j - 1], dp[row][col + (1 << (j - 1))][i][j - 1]);
                            d[row][col][i][j] = min(d[row][col][i][j - 1], d[row][col + (1 << (j - 1))][i][j - 1]);
                        }
                    }
            }
        }

            while(k--)
            {
                int l, r;
                scanf("%d%d", &l, &r);
                printf("%d
", rmq(l, r, l+b-1, r+b-1));

            }
    }

    return 0;
}