Elearning CodePath – CTP Online Judge

Bài Tập Nhảy Cột

JUM

🟢 Hard #Stack #Dynamic Programming

### 📌 Thông tin chung

---

### 📝 Bài toán

Cho một dãy gồm $N$ cây cột, cây cột thứ $i$ có chiều cao là $H_i$. Hoàng tử sẽ thực hiện một bài tập nhảy từ cột này sang cột khác theo quy tắc sau:

Giả sử hoàng tử đang đứng ở cây cột thứ $i$ ($1 \le i \le N$). Bước nhảy tiếp theo sẽ là tới cây cột thứ $j$ ($i < j \le N$) thỏa mãn hai điều kiện:

1. **Chiều cao lớn hơn:** Chiều cao của cột đích phải lớn hơn chiều cao của cột hiện tại, tức là $H_j > H_i$.
2. **Gần nhất về phía phải:** Cột $j$ phải là cây cột đầu tiên về phía bên phải của cột $i$ thỏa mãn điều kiện (1). Hay nói cách khác, $j$ là chỉ số nhỏ nhất ($j = \min \{k | i < k \le N \text{ và } H_k > H_i\}$).

Bài tập kết thúc khi hoàng tử không thể thực hiện bước nhảy nào nữa (tức là không tìm được cột $j$ thỏa mãn).

**Độ hiệu quả** của bài tập được tính bằng **tổng số bước nhảy** tối đa mà hoàng tử có thể thực hiện được từ điểm xuất phát.

Nhà vua đặt ra $Q$ câu hỏi. Câu hỏi thứ $k$ có dạng $S_k$, yêu cầu tính độ hiệu quả của bài tập nếu chọn cây cột thứ $S_k$ làm điểm xuất phát.

---

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

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

* **Dòng 1:** Hai số nguyên dương $N$ và $Q$, cách nhau một khoảng trắng.
* **Dòng 2:** $N$ số nguyên dương $H_1, H_2, \dots, H_N$, biểu diễn chiều cao của các cây cột, cách nhau một khoảng trắng.
* **$Q$ dòng tiếp theo:** Dòng thứ $k$ ghi một số nguyên dương $S_k$ – chỉ số của cây cột được chọn làm điểm xuất phát cho câu hỏi thứ $k$.

**Giới hạn (Ràng buộc):**
$$
\begin{array}{l}
1 \le N, Q \le 10^5 \\
1 \le H_i \le 10^9 \\
1 \le S_k \le N
\end{array}
$$

---

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

Ghi ra file `jum.out` gồm $Q$ dòng. Dòng thứ $k$ là kết quả trả lời cho câu hỏi thứ $k$, tức là tổng số bước nhảy tối đa bắt đầu từ cột $S_k$.

---

### ✨ Ví dụ

| Input (`jum.inp`) | Output (`jum.out`) |
| :--- | :--- |
| `5 5` `1 3 4 2 5` `1` `2` `3` `4` `5` | `3` `2` `1` `1` `0` |

---

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

Cho dãy chiều cao $H = [1, 3, 4, 2, 5]$ ($N=5$).

* **Xuất phát từ cột 1 (Giá trị 1):**
    * $1 \to 2$ ($H_2=3 > 1$, là cột gần nhất).
    * $2 \to 5$ ($H_5=5 > 3$, là cột gần nhất).
    * $5 \to$ Không nhảy được. $\implies$ Tổng số bước: **3**.
    * (Dãy nhảy: $1 \to 2 \to 5$)
* **Xuất phát từ cột 2 (Giá trị 3):**
    * $2 \to 3$ ($H_3=4 > 3$, là cột gần nhất).
    * $3 \to 5$ ($H_5=5 > 4$, là cột gần nhất).
    * $5 \to$ Không nhảy được. $\implies$ Tổng số bước: **2**.
    * (Dãy nhảy: $2 \to 3 \to 5$)
* **Xuất phát từ cột 3 (Giá trị 4):**
    * $3 \to 5$ ($H_5=5 > 4$, là cột gần nhất).
    * $5 \to$ Không nhảy được. $\implies$ Tổng số bước: **1**.
* **Xuất phát từ cột 4 (Giá trị 2):**
    * $4 \to 5$ ($H_5=5 > 2$, là cột gần nhất).
    * $5 \to$ Không nhảy được. $\implies$ Tổng số bước: **1**.
* **Xuất phát từ cột 5 (Giá trị 5):**
    * $5 \to$ Không nhảy được. $\implies$ Tổng số bước: **0**.

---

### 💡 Gợi ý thuật toán

Bài toán này có thể được giải quyết hiệu quả bằng hai bước:

1.  **Xử lý trước (Preprocessing):** Tìm ra cột nhảy tiếp theo $Next[i]$ từ mỗi cột $i$.
    * Sử dụng **Stack đơn điệu (Monotonic Stack)** để tìm cột gần nhất bên phải có giá trị lớn hơn cho mỗi cột $i$ trong thời gian $O(N)$.
    * $Next[i]$: chỉ số cột mà hoàng tử nhảy tới từ cột $i$. Nếu không nhảy được, $Next[i] = 0$ (hoặc $N+1$).

2.  **Lập trình Động (Dynamic Programming) hoặc Đệ quy có nhớ:** Tính số bước nhảy tối đa $Count[i]$ từ mỗi cột $i$.
    * Công thức truy hồi: $Count[i] = 1 + Count[Next[i]]$.
    * Trường hợp cơ sở: Nếu $Next[i] = 0$, thì $Count[i] = 0$.
    * Tính toán $Count[i]$ từ $i=N$ về $i=1$ trong thời gian $O(N)$.

Tổng độ phức tạp thời gian là **$O(N + Q)$**, rất hiệu quả.

---

### 🧪 Phân Subtask & Ràng buộc

✅ Đã AC: 1 / 3 submissions