Problem 58: 2D Range Minimum Query

Problem Statement: Given a 2D matrix, preprocess it to answer queries: for given indices (r1, c1, r2, c2), return the minimum value in the submatrix defined by these coordinates.

Input

The first line contains two integers n and m. The next n lines each contain m integers. Then an integer q is given followed by q lines, each containing four integers: r1, c1, r2, c2.

Output

For each query, print the minimum value in the specified submatrix.

Examples


Input:
3 3
1 2 3
4 5 6
7 8 9
2
1 1 2 2
2 2 3 3

Output:
1
5

Solution Explanation

2D Sparse Table can be built in O(n*m*logn*logm) time and each query answered in O(1). Precompute minima for all submatrices of sizes 2^k by 2^l.

Solution in C++


#include 
#include 
#include 
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector> mat(n, vector(m));
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> mat[i][j];
        }
    }
    int logn = log2(n) + 1;
    int logm = log2(m) + 1;
    vector>>> st(logn, vector>>(logm, vector>(n, vector(m))));
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            st[0][0][i][j] = mat[i][j];
        }
    }
    for (int a = 0; a < logn; a++){
        for (int b = 0; b < logm; b++){
            if(a == 0 && b == 0) continue;
            for (int i = 0; i + (1 << a) - 1 < n; i++){
                for (int j = 0; j + (1 << b) - 1 < m; j++){
                    if(a == 0)
                        st[a][b][i][j] = min(st[a][b-1][i][j], st[a][b-1][i][j + (1 << (b - 1))]);
                    else if(b == 0)
                        st[a][b][i][j] = min(st[a-1][b][i][j], st[a-1][b][i + (1 << (a - 1))][j]);
                    else {
                        int m1 = min(st[a-1][b-1][i][j], st[a-1][b-1][i + (1 << (a - 1))][j]);
                        int m2 = min(st[a-1][b-1][i][j + (1 << (b - 1))], st[a-1][b-1][i + (1 << (a - 1))][j + (1 << (b - 1))]);
                        st[a][b][i][j] = min(m1, m2);
                    }
                }
            }
        }
    }
    int q; 
    cin >> q;
    while(q--){
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2; 
        r1--; c1--; r2--; c2--;
        int k1 = log2(r2 - r1 + 1);
        int k2 = log2(c2 - c1 + 1);
        int m1 = min(st[k1][k2][r1][c1], st[k1][k2][r2 - (1 << k1) + 1][c1]);
        int m2 = min(st[k1][k2][r1][c2 - (1 << k2) + 1], st[k1][k2][r2 - (1 << k1) + 1][c2 - (1 << k2) + 1]);
        cout << min(m1, m2) << "\n";
    }
    return 0;
}