10293: CF EDU - Segment Tree P2 - Step 4 - A. Assignment, Addition, and Sum
[Creator : ]
Description
There is an array of $n$ elements, initially filled with zeros. You need to write a data structure that processes three types of queries:
- assign value $v$ to all elements on the segment from $l$ to $r−1$,
- add $v$ to all elements on the segment from $l$ to $r−1$,
- find the sum on the segment from $l$ to $r−1$.
Input
The first line contains two numbers $n,m\ (1≤n,m≤100,000)$, the size of the array and the number of operations.
The following lines contain the description of the operations. The description of each operation is as follows:
The following lines contain the desc
- 1 l r v: assign $v$ to the segment from $l$ to $r−1\ (0≤l<r≤n,\ 0≤v≤10^5)$.
- 2 l r v: add $v$ to the segment from $l$ to $r−1\ (0≤l<r≤n,\ 0≤v≤10^5)$.
- 3 l r: find the sum on the segment from $l$ to $r−1\ (0≤l<r≤n)$.
Output
For each operation of the third type, print the corresponding value.
Sample 1 Input
5 7
1 0 3 3
2 2 4 2
3 1 3
2 1 5 1
1 0 2 2
3 0 3
3 3 5
Sample 1 Output
8
10
4