💻
Elearning
CodePath
Problems
Contests
Roadmap
🔐 Login
Cập Nhật Nhân và Truy Vấn Tổng Đoạn
SEG006
### 📌 Thông tin chung | Mục | Chi tiết | | :--- | :--- | | **Tên File Input** | `RANGEMUL.INP` | | **Tên File Output** | `RANGEMUL.OUT` | | **MODULO** | $10^9 + 7$ | --- ### 📝 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` - nhân giá trị tất cả các phần tử trong đoạn $[L, R]$ với $W$. $ A_i \leftarrow A_i \times W, \quad \forall i \in [L, R]$ 2. **Loại 2 (Truy vấn):** `2 L, R` - tính tổng giá trị các phần tử trong đoạn $[L, R]$, kết quả lấy dư cho $10^9 + 7$. $ \sum_{i=L}^{R} A_i \pmod{10^9 + 7}$ 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 (tổng giá trị đoạn $[L, R]$ chia cho $10^9 + 7$). --- ### ✨ 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` | `19` <br> `62` | 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] \times 2$. * $A$ mới: $[1, 2\times 2, 3\times 2, 4\times 2, 5] = [1, 4, 6, 8, 5]$. 2. **Thao tác `2 3 5`:** Tính tổng $A[3..5]$. * $6 + 8 + 5 = 19$. Output: **19**. 3. **Thao tác `1 1 4 3`:** $A[1..4] \leftarrow A[i] \times 3$. * $A$ mới: $[1\times 3, 4\times 3, 6\times 3, 8\times 3, 5] = [3, 12, 18, 24, 5]$. 4. **Thao tác `2 1 5`:** Tính tổng $A[1..5]$. * $3 + 12 + 18 + 24 + 5 = 62$. Output: **62**. Tất cả các kết quả đều nhỏ hơn $10^9 + 7$, nên kết quả modulo chính là kết quả. --- ### 🏷 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: 6 / 15 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