Elearning CodePath – CTP Online Judge

Tổng Dãy Con Lớn Nhất trên Đoạn

SEG002

🟢 Medium #Segment Tree #Interval #Data Structure

### 📌 Thông tin chung

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

Ban đầu có $N$ hộp quà, hộp thứ $i$ có giá trị điểm $A[i]$ (có thể âm).
Nam được quyền chọn một dãy con liên tiếp trong đoạn $[L, R]$ đã cho, và điểm số là tổng giá trị điểm của các hộp trong dãy đó.

Yêu cầu: Với mỗi yêu cầu của Ban tổ chức, bạn cần giúp Nam tìm số điểm lớn nhất có thể đạt được.

Các thao tác (truy vấn) của Ban tổ chức:

1.  **Truy vấn (Type 1):** Đưa ra một đoạn $[L, R]$ ($1 \le L \le R \le N$) và yêu cầu Nam tìm tổng dãy con liên tiếp lớn nhất (Maximum Subarray Sum) nằm hoàn toàn trong đoạn $[L, R]$ đó.
    * Tức là tìm $\max(\sum_{i=X}^{Y} A[i])$ với $L \le X \le Y \le R$.
2.  **Cập nhật (Type 2):** Tăng giá trị điểm của một hộp $X$ bất kì lên một lượng $W$.
    $    A[X] \leftarrow A[X] + W $

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

* Dòng đầu tiên: Hai số nguyên dương $N$ và $Q$ là số thao tác của Ban tổ chức.
* Dòng thứ hai: $N$ số nguyên $A[i]$ là giá trị điểm ban đầu của các hộp.
* $Q$ dòng tiếp theo mỗi dòng gồm:
    * **Nếu $T = 1$:** Nhập $2$ số nguyên dương $L, R$ ($1 \le L \le R \le N$). (Yêu cầu trả lời)
    * **Nếu $T = 2$:** Nhập $1$ số nguyên dương $X$ ($1 \le X \le N$) và $1$ số nguyên $W$ ($|W| \le 10^9$). (Cập nhật điểm)

Giới hạn:
* $N, Q \le 5 \times 10^4$.
* $|A[i]| \le 10^9$.
* $|W| \le 10^9$.

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

Gồm $Q$ dòng, với mỗi dòng là số điểm lớn nhất có thể đạt được với mỗi đoạn $[L, R]$ tương ứng (truy vấn loại 1).

---
### ✨ Ví dụ

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

Giải thích: $A = [3, -2, 1, 4, -5, 8, -10, 5, -2, 6]$.

1.  **Type 1 (1, 5):** Tìm $\max$ subarray sum trong $[3, -2, 1, 4, -5]$.
    * Dãy con lớn nhất: $[1, 4]$ (vị trí 3 đến 4). Tổng: $1 + 4 = 5$.
    * Dãy con lớn nhất: $[3, -2, 1, 4]$. Tổng: $3 - 2 + 1 + 4 = 6$. Output: **6**.
2.  **Type 2 (5, -1):** $A[5] \leftarrow A[5] + (-1)$. $A[5] = -5 - 1 = -6$.
    * $A$ mới: $[3, -2, 1, 4, \mathbf{-6}, 8, -10, 5, -2, 6]$.
3.  **Type 1 (4, 9):** Tìm $\max$ subarray sum trong $[4, -6, 8, -10, 5, -2]$.
    * Dãy con lớn nhất: $[8]$ (vị trí 6). Tổng: $8$. Output: **8**.
4.  **Type 1 (2, 7):** Tìm $\max$ subarray sum trong $[-2, 1, 4, -6, 8, -10]$.
    * Dãy con lớn nhất: $[1, 4, -6, 8]$. Tổng: $1+4-6+8 = 7$.
    * Dãy con lớn nhất: $[8]$ (vị trí 6). Tổng: $8$. Output: **8**.

---
### 🏷 Subtasks

| Subtask | Ràng buộc | Yêu cầu chính | Tỷ lệ điểm |
| :--- | :--- | :--- | :--- |
| $1$ | $N, Q \le 1000$ |  $30\%$ |
| $2$ | $N, Q \le 5 \times 10^4$ | $70\%$ |

---

✅ Đã AC: 0 / 0 submissions