P6707 [COCI 2010/2011 #7] UPIT

Mirko 厌倦了为了各种任务去实现各种数据结构。所以，他决定写一个终极数据结构去操纵他最喜欢的数字序列。 快来帮助他吧！ Mirko 会给你他的数列，以及一系列你必须执行的操作。每个询问要么询问关于数列的信息，要么修改现有的数列。下面列出了所有可能的操作类型。 查询种类|描述|例子| :-:|:-:|:-: `1 A B X`|将 $[A,B]$ 中所有元素值更改为 $X$|$(9, 8, 7, 6, 5, 4, 3, 2, 1)\to$ $1$ $3$ $5$ $0$ $\to$ $(9, 8, 0, 0, 0, 4, 3, 2, 1)$ `2 A B X`|将 $[A,B]$ 中所有元素增加一数，第 $A+k$ 位增加 $(k+1) \times X$|$(9, 8, 7, 6, 5, 4, 3, 2, 1)\to$ $2$ $3$ $5$ $2$ $\to (9, 8, 9, 10, 11, 4, 3, 2, 1)$ `3 C X`|在原来的第 $C$ 位前插入一个数，数值为 $X$|$(9, 8, 7, 6, 5, 4, 3, 2, 1)$ $\to$ $3$ $4$ $100$ $\to$ $(9, 8, 7, 100, 6, 5, 4, 3, 2, 1)$ `4 A B`|查询 $[A,B]$ 的数值和|$(2, 18, 7, 6, 1, 4, 7, 7, 2)$ $\to$ $4$ $6$ $7$ $\to$ $result: 11$

给定一个数列 $f$ ，有以下操作。 设数列当前长度为 $n$。 |查询种类|描述| |:-:|:-:| `1 A B X`| $f_i=X(A \le i \le B)$ `2 A B X`| $f_i+=(i-A+1) \times X(A \le i \le B)$ `3 C X`| $f_{i+1}=f_i(C \le i \le n)$ $f_C=X$ `4 A B`| 求$\sum^B_{i=A}f_i$

第一行两个正整数 $n$ , $Q$，分别表示数列初始长度和操作数量。 第二行 $n$ 个非负整数表示初始数列。 接下来 $Q$ 行每行各包含一个如上询问。

对于每一个 $4$ 号操作，输出一行答案。

#### 数据规模及约定 设当前数列长 $t$。 对于 $100\%$ 的数据 $1 \le n$ , $Q \le 1 \times 10^5$ , $f_i \le 1 \times 10^5$ , $1 \le X \le 100$ , $1 \le A \le B \le t$ , $1 \le C \le t + 1$。 #### 说明 本题满分 $130$ 分。 译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #7](https://hsin.hr/coci/archive/2010_2011/contest7_tasks.pdf) T6 UPIT。