---
# System prepended metadata

title: Cubill Ghét Làm Việc Nhà

---

Nguồn: (Dựa trên bài https://oj.vnoi.info/problem/segtree_itmix).
Rating : 2100.

**Đề Bài**:
Do Cubill quá lười học nên mẹ cậu phạt cậu bằng cách cho cậu một dãy số $a$ gồm $n$ số $a_1, a_2, ..., a_n$. Cậu mỗi ngày phải chăm sóc nó theo yều cầu của mẹ trong $q$ ngày, có 5 loại việc cậu cần làm mỗi ngày:

* Loại 1 có dạng $l, r, x$ cậu tăng các số $a_l, a_{l+1},..., a_r$ lên $x$ đơn vị.  
* Loại 2 có dạng $l, r, x$ cậu nhân các số $a_l, a_{l+1},..., a_r$ lên $x$ lần.
* Loại 3 có dạng $l, r, x$ cậu gán các số $a_l, a_{l+1},..., a_r$ thành $x$.
* Loại 4 có dạng $l, r$ cậu tính giúp mẹ $\sum_{i=l}^r a_i$.
* Loại 5 có dạng $l, r$ cậu tính giúp mẹ $\sum_{i=l}^r \sum_{j=i+1}^r (a_i*a_j)$.

Cubill cần thời gian để chơi game nên bạn có thể giúp cậu ấy không ?
**Input**:
* Dòng đầu chứa hai số nguyên $n, q$ ($n, q \le 10^5$) là độ dãy dãy $a$ và số ngày mẹ cậu yêu cầu cậu chăm sóc dãy $a$.
* Dòng thứ hai chứa $n$ số nguyên $a_1, a_2,..., a_n$ ($|a_i| \le 10^9$) thể hiện dãy $a$
* $q$ dòng tiếp theo thể hiện việc mẹ cậu giao mỗi ngày:
Đầu dòng là số $t$ thể hiện loại công việc mẹ cậu yêu cầu.
Nếu $t \le 3$ tiếp theo là ba số nguyên $l, r, x$. ($l < r \le n, |x| \le 10^9$)
Nếu $t={4, 5}$ tiếp theo là hai số nguyên $l, r$.($l < r \le n$)


**Output**:
* Mỗi dòng là đáp án cho công việc $4, 5$ tương ứng theo đúng thứ tự xuất hiện dưới dạng mod của $10^9+7$.

**Scoring:**

| Subtask  | Điểm     | Giới Hạn |
| -------- | -------- | -------- |
| 1     | 30     | Mẹ cậu chỉ giao việc loại $1, 4$     |
| 1     | 30     | Mẹ cậu chỉ giao việc loại $4, 5$     |
| 2     | 40     | Không có ràng buộc gì thêm |

**Lời Giải:**
Trước Tiên mình nghĩ các bạn nên AC bài [sau đây](https://oj.vnoi.info/problem/segtree_itmix) trước khi làm bài này.
Subtask 1: 
Do chỉ gồm việc 1 và 4 nên bài toán trở thành bài segment tree cơ bản.
Subtask 2:
Các bạn cần phải viết được ra công thức sau:
$\sum_{i=l}^r \sum_{j=i+1}^r (a_i*a_j) = ((\sum_{i=l}^r a_i)^2-(\sum_{i=l}^r a_i^2))/2$.
Từ đó để query tổng một đoạn nhanh ta sử dụng 2 mảng prefixsum.
Subtask 3:
Tương tự subtask 2 những ta phải dựng hai cái segment tree một cái lưu tổng của các $a[i]$, một lưu tổng của các $a[i]^2$.
Nhớ bước $/2$ thì nghịch đảo modulo nhé.

**Code** : https://ideone.com/l83d9q