P6707 [COCI 2010/2011 #7] UPIT

Mirko is tired of implementing different data structures for different tasks. So, he decided to write one ultimate data structure to handle his favorite sequence of numbers. Come and help him! Mirko will give you his sequence, as well as a series of operations you must perform. Each query either asks for information about the sequence or modifies the existing sequence. All possible operation types are listed below. Query type | Description | Example :-: | :-: | :-: `1 A B X` | Change all elements in $[A,B]$ to $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` | Increase all elements in $[A,B]$ by a value: position $A+k$ increases by $(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` | Insert a number with value $X$ before the original position $C$ | $(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` | Query the sum of values in $[A,B]$ | $(2, 18, 7, 6, 1, 4, 7, 7, 2)$ $\to$ $4$ $6$ $7$ $\to$ $result: 11$

Given a sequence $f$, the following operations are supported. Let the current length of the sequence be $n$. | Query type | Description | |:-:|:-:| `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`| Compute $\sum^B_{i=A} f_i$.

The first line contains two positive integers $n$ and $Q$, representing the initial length of the sequence and the number of operations. The second line contains $n$ non-negative integers, representing the initial sequence. The next $Q$ lines each contain one query as described above.

For each type $4$ operation, output one line with the answer.

#### Constraints Let the current sequence length be $t$. For $100\%$ of the testdata: $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$. #### Notes This problem is worth $130$ points in total. Translated from [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #7](https://hsin.hr/coci/archive/2010_2011/contest7_tasks.pdf) T6 UPIT. Translated by ChatGPT 5