Paint and Sum

Difficulty: 1400 6000 ms 128 MB

lazy-propagation segment-tree

Support P l r v — assign v to every element of a_l..r — and Q l r — print the sum of a_l..r.

Input: the first line has N and Q; the second line has the array; each of the next Q lines is an operation.

Output: one line per query.

Constraints:

• 1 ≤ N, Q ≤ 10⁵ (tests use N, Q ≤ 1500)
• 0 ≤ values, v ≤ 1000

Sample Tests

5 3
1 2 3 4 5
Q 1 5
P 2 4 0
Q 1 5

15
6

1 1
7
Q 1 1

7

Read the Editorial