Sum of Squares with Segment Tree
Segment trees are extremely useful. In particular "Lazy Propagation" (for example allows one to compute sums over a range in O(lg(n)) and update ranges in O(lg(n)) as well. In this problem you will compute the sum of squares over a range with range updates of two types:
increment in a range
set all numbers the same in a range.
Input
First line contains number of test cases. First line of each test contains two positive integers n (n ≤ 10^5) and q (q ≤ 10^5). The next line contains n integers, each no more than 1000 by absolute value. Each of the next q lines starts with a number, which indicates the type of operation:
2 st nd – return the sum of the squares of the numbers with indices in [st, nd] {i.e., from st to nd inclusive} (1 ≤ st ≤ nd ≤ n).
1 st nd x – add "x" to all numbers with indices in [st, nd] (1 ≤ st ≤ nd ≤ n, and -1000 ≤ x ≤ 1000).
0 st nd x – set all numbers with indices in [st, nd] to "x" (1 ≤ st ≤ nd ≤ n, and -1000 ≤ x ≤ 1000).
Output
For each test case output the “Case <caseno>:” in the first line and from the second line output the sum of squares for each operation of type 2. Intermediate overflow will not occur with proper use of 64-bit signed integer.