SEGSQRSS  Sum of Squares with Segment Tree
Segment trees are extremely useful. In particular "Lazy Propagation" (i.e. see here, 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 something much harder:
The sum of squares over a range with range updates of 2 types:
1) increment in a range
2) set all numbers the same in a range.
Input
There will be T (T <= 25) test cases in the input file. First line of the input contains two positive integers, N (N <= 100,000) and Q (Q <= 100,000). The next line contains N integers, each at most 1000. 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 1,000 <= x <= 1,000).
0 st nd x  set all numbers with indices in [st, nd] to "x" (1 <= st <= nd <= N, and 1,000 <= x <= 1,000).
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 64bit signed integer.
Example
Input: 2 4 5 1 2 3 4 2 1 4 0 3 4 1 2 1 4 1 3 4 1 2 1 4 1 1 1 2 1 1 Output: Case 1: 30 7 13 Case 2: 1
hide comments
anonymous:
20140702 01:03:09
cake walk...AC without lazy propagation...:)


GURVINDER SINGH:
20140604 19:12:30
Got wa for printing case #%d :( silly me :p 

Ashwin. K:
20130423 16:38:39
um. Test cases are very weak.


Chen Xiaohong:
20120711 22:01:53
Thanks! This is now fixed. Note also that "x" can be 0 for the set operation (it's 1000 <= x <= 1000). Also note that increments can happen after sets, and sets can happen after increments. Rejudged after fixing this also in the dataset.


Buda IM (retired):
20120711 22:01:26
I don't think input example is correct. You have 5 queries, but Q=4 
Added by:  Chen Xiaohong 
Date:  20120711 
Time limit:  1.106s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 