💻
Elearning
CodePath
Problems
Contests
Roadmap
🔐 Login
Cập Nhật Tăng và Truy Vấn Max Đoạn
SEG005
### 📌 Thông tin chung | Mục | Chi tiết | | :--- | :--- | | **Tên File Input** | `RANGEMAX.INP` | | **Tên File Output** | `RANGEMAX.OUT` | --- ### 📝 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` <br> `1 2 3 4 5` <br> `1 2 4 2` <br> `2 3 5` <br> `1 1 4 3` <br> `2 1 5` | `6` <br> `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
⬅ 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