Elearning CodePath – CTP Online Judge

Truy vấn Min/Max trên Đoạn Một Chiều

RMQ1D

🟢 Easy #General

### 📌 Thông tin chung

---

### 📝 Bài toán

Cho dãy số nguyên $A = (A_1, A_2, \dots, A_N)$.

Yêu cầu: Trả lời $Q$ truy vấn. Mỗi truy vấn có dạng hai số nguyên $L$ và $R$ ($1 \le L \le R \le N$). Với mỗi truy vấn, hãy in ra hai giá trị:

1.  **Giá trị lớn nhất** (Maximum) trong đoạn $A[L..R]$.
2.  **Giá trị nhỏ nhất** (Minimum) trong đoạn $A[L..R]$.

$$
\text{Truy vấn } (L, R): \quad \max(A[L..R]) \text{ và } \min(A[L..R])
$$

---

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

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

* **Dòng 1:** Số nguyên dương $N$ – độ dài dãy.
* **Dòng 2:** $N$ số nguyên $A_1, A_2, \dots, A_N$ (các phần tử của dãy), cách nhau một khoảng trắng.
* **Dòng 3:** 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 hai số nguyên $L$ và $R$, cách nhau một khoảng trắng.

**Giới hạn (Ràng buộc):**
* $1 \le N \le 10^5$
* $-10^9 \le A_i \le 10^9$
* $1 \le Q \le 10^5$
* $1 \le L \le R \le N$

---

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

Ghi ra file `RMQ1D.OUT` gồm $Q$ dòng, mỗi dòng ghi kết quả của truy vấn tương ứng. Với mỗi truy vấn, in ra hai giá trị: **Maximum** và **Minimum**, cách nhau một khoảng trắng.

---

### ✨ Ví dụ

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

---

### 🧪 Giải thích Ví dụ

Dãy $A = [3, 2, 4, 5, 1, 7, 6]$.

1.  **Truy vấn $(1, 7)$:** Đoạn $[3, 2, 4, 5, 1, 7, 6]$.
    * $\max = 7$, $\min = 1$. $\implies$ **7 1**
2.  **Truy vấn $(3, 6)$:** Đoạn $[4, 5, 1, 7]$.
    * $\max = 7$, $\min = 1$. $\implies$ **7 1**
3.  **Truy vấn $(2, 4)$:** Đoạn $[2, 4, 5]$.
    * $\max = 5$, $\min = 2$. $\implies$ **5 2**

✅ Đã AC: 0 / 11 submissions