## 2-Dimensional Range Minimum Query

View as PDF

Points: 17 (partial)
Time limit: 2.0s
Memory limit: 1G

Author:
Problem type
Allowed languages
C++

You are given a -dimensional array of integers of size . We will call this array . You are then required to answer multiple queries for the minimum integer in a given submatrix.

Formally, given integers , determine .

#### Implementation Details

You should implement the following functions:

void init(std::vector<std::vector<int>> arr);

• : a -dimensional array of size .
int query(int a, int b, int c, int d);

• : the lower bound on the first dimension of the submatrix.
• : the upper bound on the first dimension of the submatrix.
• : the lower bound on the second dimension of the submatrix.
• : the upper bound on the second dimension of the submatrix.
• This function should return the minimum integer in the submatrix formed by .

It is guaranteed that init will be called exactly once, and that this call will be made before any calls to query.

#### Constraints

for
for all calls to query
for all calls to query

Disclaimer: were generated randomly.
Your answer will be considered correct if the bitwise of the answers to all the queries matches the expected result.

query will be called at most times.

query will be called at most times.

query will be called at most times.

query will be called at most times.

#### Sample Interaction

Please note that the sample will not appear in any of the test cases.

Function Call Return Value
init({{1, 2}, {3, 4}})
query(0, 1, 0, 1) 1
query(1, 1, 0, 1) 3
query(0, 0, 1, 1) 2