Elearning CodePath – CTP Online Judge

Cập Nhật Tăng và Truy Vấn Max Đoạn

SEG005

🟢 Medium #Segment Tree #Interval #Data Structure

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho dãy $A$ gồm $N$ phần tử và $Q$ truy vấn. Có 2 loại truy vấn:

1.  **Loại 1 (Cập nhật):** `1 L, R, W` - tăng giá trị tất cả các phần tử trong đoạn $[L, R]$ lên một lượng $W$.
    $    A_i \leftarrow A_i + W, \quad \forall i \in [L, R]$
2.  **Loại 2 (Truy vấn):** `2 L, R` - tính giá trị lớn nhất (Maximum) trong đoạn $[L, R]$.
    $    \max_{i=L}^{R} (A_i)$

Giới hạn tham số:
* $L, R, W$ là các số nguyên dương.
* $1 \le L \le R \le N$.
* $W \le 10^9$.

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

* Dòng đầu chứa hai số nguyên dương $N$ và $Q$ ($N, Q \le 10^5$).
* Dòng thứ hai chứa $N$ số nguyên dương $A_1, A_2, \dots, A_N$ ($A_i \le 10^9$).
* $Q$ dòng tiếp theo chứa truy vấn thuộc 1 trong 2 loại trên.

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

Câu trả lời cho các truy vấn loại 2 (giá trị lớn nhất trong đoạn $[L, R]$).

---
### ✨ Ví dụ

| Input | Output |
| :---: | :---: |
| `5 4` `1 2 3 4 5` `1 2 4 2` `2 3 5` `1 1 4 3` `2 1 5` | `6` `9` |

Giải thích ví dụ:
* $A$ ban đầu: $[1, 2, 3, 4, 5]$.
1.  **Thao tác `1 2 4 2`:** $A[2..4] \leftarrow A[i] + 2$.
    * $A$ mới: $[1, 4, 5, 6, 5]$.
2.  **Thao tác `2 3 5`:** Tính $\max$ trong $A[3..5] = [5, 6, 5]$.
    * $\max(5, 6, 5) = 6$. Output: **6**.
3.  **Thao tác `1 1 4 3`:** $A[1..4] \leftarrow A[i] + 3$.
    * $A$ mới: $[4, 7, 8, 9, 5]$.
4.  **Thao tác `2 1 5`:** Tính $\max$ trong $A[1..5] = [4, 7, 8, 9, 5]$.
    * $\max(4, 7, 8, 9, 5) = 9$. Output: **9**.

---
### 🏷 Phân tích và Ràng buộc

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- | 
| $1$ | $N, Q \le 1000$ | $30\%$ |
| $2$ | $N, Q \le 10^5$ | $30\%$ |
| $3$ | $N, Q \le 10^5$ | $40\%$ |

---

✅ Đã AC: 4 / 6 submissions