Elearning CodePath – CTP Online Judge

Tính Tổng Bình Phương Trên Đoạn

SEG003

🟢 Hard #Segment Tree #Data Structure

### 📌 Thông tin chung

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

Cho một mảng $A$ có độ dài vô tận. Ban đầu tất cả các phần tử của dãy đều bằng 0 ($A[i] = 0$). Ta có 2 loại thao tác:

1.  **Cập nhật (Type 1):** Tăng tất cả các phần tử của mảng $A$ trong đoạn $[l, r]$ lên một lượng $val$.
    $   A[i] \leftarrow A[i] + val, \quad \forall i \in [l, r]$
2.  **Truy vấn (Type 0):** Cần tính tổng bình phương các phần tử trong đoạn $[l, r]$:
    $    \sum_{i=l}^{r} A[i]^2$

Yêu cầu: Với mỗi thao tác loại 0, in ra đáp án cần tìm. Vì kết quả có thể rất to nên ta chỉ cần in kết quả lấy dư cho $10^9 + 7$.

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

* Dòng đầu tiên là số nguyên $Q$ là số thao tác.
* $Q$ dòng tiếp theo, mỗi dòng có dạng 1 trong 2 loại thao tác:
    * **Type 1:** Gồm $1\ l\ r\ val$ (Cập nhật đoạn $[l, r]$ thêm $val$).
    * **Type 0:** Gồm $0\ l\ r$ (Truy vấn tổng bình phương đoạn $[l, r]$).

Giới hạn:
* $Q \le 10^5$.
* $l \le r \le 10^9$.
* $val \le 10^9$.

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

Với mỗi thao tác loại 0, in ra đáp án cần tìm $\pmod{10^9 + 7}$.

---
### ✨ Ví dụ

| Input | Output |
| :---: | :---: |
| `5` `1 1 5 3` `0 2 3` `1 3 7 2` `1 4 5 2` `0 1 7` | `18` `149` |

Giải thích ví dụ (Sử dụng chỉ số 1-based, chỉ xét các phần tử có giá trị $\ne 0$):

1.  **Ban đầu:** $A = [0, 0, 0, \dots]$.
2.  **Thao tác `1 1 5 3`:** $A[1..5] \leftarrow A[i] + 3$. $A = [3, 3, 3, 3, 3, 0, \dots]$.
3.  **Thao tác `0 2 3`:** Tính $\sum_{i=2}^{3} A[i]^2$.
    * $A[2]^2 + A[3]^2 = 3^2 + 3^2 = 9 + 9 = 18$. Output: **18**.
4.  **Thao tác `1 3 7 2`:** $A[3..7] \leftarrow A[i] + 2$.
    * $A$ mới: $A[1]=3, A[2]=3$.
    * $A[3]=3+2=5, A[4]=3+2=5, A[5]=3+2=5$.
    * $A[6]=0+2=2, A[7]=0+2=2$.
    * $A = [3, 3, 5, 5, 5, 2, 2, 0, \dots]$.
5.  **Thao tác `1 4 5 2`:** $A[4..5] \leftarrow A[i] + 2$.
    * $A[4]=5+2=7, A[5]=5+2=7$.
    * $A = [3, 3, 5, 7, 7, 2, 2, 0, \dots]$.
6.  **Thao tác `0 1 7`:** Tính $\sum_{i=1}^{7} A[i]^2$.
    * $3^2 + 3^2 + 5^2 + 7^2 + 7^2 + 2^2 + 2^2$
    * $9 + 9 + 25 + 49 + 49 + 4 + 4 = 149$. Output: **149**.

---
### 🏷 Ràng buộc

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- | 
| $1$ | $Q \le 1000$; $r \le 1000$ | $30\%$ |
| $2$ | $Q \le 10^5$; $r \le 10^5$  | $30\%$ |
| $3$ | $Q \le 10^5$; $r \le 10^9$  | $40\%$ |

---

✅ Đã AC: 0 / 0 submissions