Elearning CodePath – CTP Online Judge

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

SEG006

🟢 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` - 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` `1 2 3 4 5` `1 2 4 2` `2 3 5` `1 1 4 3` `2 1 5` | `19` `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