Elearning CodePath – CTP Online Judge

Truy vấn Min trên Hình chữ nhật Hai Chiều

RMQ2D

🟢 Easy #General #Tree

### 📌 Thông tin chung

---

### 📝 Bài toán

Cho một bảng (mảng hai chiều) $A$ kích thước $M \times N$. Phần tử tại hàng $i$ và cột $j$ là $A_{i,j}$, với $1 \le i \le M$ và $1 \le j \le N$.

Yêu cầu: Trả lời $Q$ truy vấn. Mỗi truy vấn $k$ có dạng $x_{1}, y_{1}, x_{2}, y_{2}$, xác định một vùng hình chữ nhật trên bảng.

Với mỗi truy vấn, hãy tìm **giá trị nhỏ nhất** (Minimum) của các phần tử $A_{i,j}$ nằm trong vùng hình chữ nhật đó:
$$
\min \{A_{i,j} \mid x_1 \le i \le x_2 \text{ và } y_1 \le j \le y_2\}
$$
với $1 \le x_1 \le x_2 \le M$ và $1 \le y_1 \le y_2 \le N$.

---

### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `RMQ2D.INP` gồm:

* **Dòng 1:** Hai số nguyên dương $M$ và $N$ – kích thước số hàng và số cột của bảng.
* **$M$ dòng tiếp theo:** Dòng thứ $i$ chứa $N$ số nguyên $A_{i,1}, A_{i,2}, \dots, A_{i,N}$, cách nhau một khoảng trắng.
* **Dòng tiếp theo:** Số nguyên dương $Q$ – số lượng truy vấn.
* **$Q$ dòng cuối cùng:** Mỗi dòng mô tả một truy vấn gồm 4 số nguyên: $x_{1}, y_{1}, x_{2}, y_{2}$ (tọa độ góc trên bên trái và góc dưới bên phải).

**Giới hạn (Ràng buộc):**
* $1 \le M, N \le 500$
* $1 \le Q \le 200,000$
* $-2^{31} \le A_{i,j} \le 2^{31}-1$ (Giá trị $A_{i,j}$ nằm trong phạm vi của số nguyên 32-bit có dấu)
* $1 \le x_1 \le x_2 \le M$
* $1 \le y_1 \le y_2 \le N$

---

### 📤 Định dạng Đầu ra

Ghi ra file `RMQ2D.OUT` gồm $Q$ số nguyên, mỗi số trên một dòng riêng biệt, là kết quả nhỏ nhất tìm được cho truy vấn tương ứng.

---

### ✨ Ví dụ

| Input (`RMQ2D.INP`) | Output (`RMQ2D.OUT`) |
| :--- | :--- |
| `3 3` `3 4 5` `2 3 4` `5 4 3` `3` `1 1 2 2` `1 2 1 3` `1 2 3 2` | `2` `4` `3` |

✅ Đã AC: 0 / 0 submissions