Chmin Chmax Add và tổng đoạn (Range Chmin Chmax Add Range Sum)

Nguồn: Library Checker

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

Đề bài

Cho dãy số nguyên $a_0,a_1,\ldots,a_{N-1}$. Xử lý $Q$ truy vấn trên đoạn nửa mở $[l,r)$:

• 0 l r b: $a_i\leftarrow\min(a_i,b)$ cho mọi $l\le i<r$.
• 1 l r b: $a_i\leftarrow\max(a_i,b)$ cho mọi $l\le i<r$.
• 2 l r b: $a_i\leftarrow a_i+b$ cho mọi $l\le i<r$.
• 3 l r: in $\sum_{i=l}^{r-1}a_i$.

Input

Dòng đầu chứa $N,Q$. Dòng thứ hai chứa $N$ số $a_0,\ldots,a_{N-1}$. Mỗi trong $Q$ dòng sau là một query loại 0, 1, 2 hoặc 3 như mô tả.

Output

Với mỗi query loại 3, in tổng đoạn trên một dòng.

Subtask

• Subtask 1 (20%): N,Q≤30; các điều kiện khác giữ như bài đầy đủ.

• Subtask 2 (30%): N,Q≤3000; các điều kiện khác giữ như bài đầy đủ.

• Subtask 3 (50%): toàn bộ giới hạn:

• $1\le N,Q\le2\cdot10^5$

• $0\le l<r\le N$

• trong toàn bộ quá trình luôn có $|a_i|\le10^{12}$

Ví dụ

Input

5 8
1 2 3 4 5
3 0 5
0 1 5 3
3 0 5
1 0 3 2
2 2 5 4
3 1 4
0 0 5 6
3 0 5

Output

15
12
16
22

Giải thích

Từ [1,2,3,4,5], chmin [1,5) 3 cho [1,2,3,3,3], tổng 12. chmax [0,3) 2 cho [2,2,3,3,3]; sau add [2,5) 4 dãy thành [2,2,7,7,7].