Editorial for 2-Dimensional Range Minimum Query

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: wleung_bvg

This editorial will not go through specific implementation details.

Let $Q$ $Q$ be the number of queries.

Subtask 1

Check all elements in the submatrix.

Time Complexity: $\mathcal O(Q \cdot N^2)$ $O (Q \cdot N^{2})$
Memory Complexity: $\mathcal O(N^2)$ $O (N^{2})$

Subtask 2

Build $N$ $N$ segment trees.

Time Complexity: $\mathcal O(N^2 + Q \cdot N \cdot \log N)$ $O (N^{2} + Q \cdot N \cdot \log N)$
Memory Complexity: $\mathcal O(N^2)$ $O (N^{2})$

Subtask 2 Alternative Solution

Build $N$ $N$ sparse tables.

Time Complexity: $\mathcal O(N^2 \cdot \log N + Q \cdot N)$ $O (N^{2} \cdot \log N + Q \cdot N)$
Memory Complexity: $\mathcal O(N^2 \cdot \log N)$ $O (N^{2} \cdot \log N)$

Subtask 3

Build a $2$ $2$ -dimensional segment tree.

Time Complexity: $\mathcal O(N^2 + Q \cdot \log^2 N)$ $O (N^{2} + Q \cdot \log^{2} N)$
Memory Complexity: $\mathcal O(N^2)$ $O (N^{2})$

Subtask 4

Build a $2$ $2$ -dimensional sparse table.

Time Complexity: $\mathcal O(N^2 \cdot \log^2 N + Q)$ $O (N^{2} \cdot \log^{2} N + Q)$
Memory Complexity: $\mathcal O(N^2 \cdot \log^2 N)$ $O (N^{2} \cdot \log^{2} N)$

Fun Solution

There are ways to abuse the randomness of the data.

Comments

There are no comments at the moment.