💻
Elearning
CodePath
Problems
Contests
Roadmap
🔐 Login
Tổng Dãy Con Lớn Nhất trên Đoạn
SEG002
### 📌 Thông tin chung | Mục | Chi tiết | | :--- | :--- | | **Tên File Input** | `MAXSUM.INP` | | **Tên File Output** | `MAXSUM.OUT`| --- ### 📝 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` <br> `3 -2 1 4 -5 8 -10 5 -2 6` <br> `1 1 5` <br> `2 5 -1` <br> `1 4 9` <br> `1 2 7` | `6` <br> `8` <br> `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
⬅ Contest
🚀 Nộp bài
💡 Gợi ý AI
📌 Bài kế
📋 Copy đề
⚙️
⬅ Contest
🚀 Nộp bài
💡 Gợi ý
📌 Bài kế
📋 Copy
📖 Hướng dẫn học tập
Học trò tri ân
☕ Một ly cà phê sẻ chia
Bạn bè ủng hộ
🍜 Một bát phở ấm lòng
💳 Quét mã ủng hộ tuỳ tâm nhé!
💬 Liên hệ Zalo!
Đóng