Tổng bình phương với cây đoạn (Sum of Squares with Segment Tree)

Nguồn: SPOJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Duy trì dãy với hai cập nhật đoạn: gán và cộng; truy vấn trả tổng bình phương các phần tử trên đoạn.

Input

Dòng đầu chứa $n,q$, dòng kế chứa mảng. Mỗi thao tác:

• 0 l r x: gán mọi phần tử $[l,r]$ thành $x$.
• 1 l r x: cộng $x$ vào mọi phần tử $[l,r]$.
• 2 l r: in $\sum_{i=l}^{r} a_i^2$.

Output

In một dòng cho mỗi truy vấn loại 2. Phiên bản PHOJ bỏ dòng Case k: của input nhiều test gốc.

Subtask

• 20 điểm: $n,q\le50$.
• 30 điểm: $n,q\le5000$.
• 50 điểm: $n,q\le10^5$, $|a_i|,|x|\le1000$; dùng số nguyên 64 bit cho giá trị trung gian.

Ví dụ

Input

4 5
1 2 3 4
2 1 4
0 3 4 1
2 1 4
1 3 4 1
2 1 4

Output

30
7
13

Giải thích

Tổng bình phương ban đầu là $1+4+9+16=30$. Gán hai phần tử cuối thành 1 cho tổng $1+4+1+1=7$. Cộng 1 cho hai phần tử cuối tạo dãy 1 2 2 2, tổng bình phương là 13.