Sum of Squares with Segment Tree#3984
Segment trees are an extremely useful data structure. For example, with lazy propagation, one can efficiently perform operations such as computing the sum over a segment in O(\log n) and updating a segment in O(\log n).
In this problem, you are required to compute the sum of squares over a given segment, while supporting two types of modifications:
Adding a given value to all elements in a segment,
Assigning a given value to all elements in a segment.
The first line contains the number of test cases.
The first line of each test case contains two integers n~(1 \le n \le 10^5) and q~(1 \le q \le 10^5).
The next line contains integers, each with absolute value not exceeding . Then follow lines, each describing one operation:
— print the sum of squares of the elements with indices from to nd~(1 \le st \le nd \le n) inclusive;
1~st~nd~x — add the value to all elements in the segment [st, nd]~(1 \le st \le nd \le n, -1000 \le x \le 1000);
0~st~nd~x — assign the value to all elements in the segment [st, nd]~(1 \le st \le nd \le n, -1000 \le x \le 1000).
For each test case, print the line "Case <caseno>:" first. Then, for each operation of type , print the sum of squares for the corresponding segment.
To avoid overflow, use a signed -bit integer data type.
Example 1