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)$ ~\mathcal O(Q \cdot N^2)~
Memory Complexity: $\mathcal O(N^2)$ ~\mathcal O(N^2)~

Subtask 2

Build $N$ ~N~ segment trees.

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

Subtask 2 Alternative Solution

Build $N$ ~N~ sparse tables.

Time Complexity: $\mathcal O(N^2 \cdot \log N + Q \cdot N)$
Memory Complexity: $\mathcal O(N^2 \cdot \log N)$ ~\mathcal 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)$ ~\mathcal O(N^2 + Q \cdot \log^2 N)~
Memory Complexity: $\mathcal O(N^2)$ ~\mathcal O(N^2)~

Subtask 4

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

Time Complexity: $\mathcal O(N^2 \cdot \log^2 N + Q)$ ~\mathcal O(N^2 \cdot \log^2 N + Q)~
Memory Complexity: $\mathcal O(N^2 \cdot \log^2 N)$ ~\mathcal 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.