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
Vipul:
20160213 07:52:37
nice problem...


spoj2121:
20151224 20:22:39
easy but lengthy to code...


karan:
20151219 19:46:41
@Rajat De : Your lazy tree may be getting overwritten. 

Sudharsansai:
20150716 20:55:26
Yeah..An easy problem (GOT AC)..But since I rarely implemented Lazy propagation, I wish someone could give me some hard test cases along with the corresponding outputs .


Jatin Narula:
20150715 22:07:39
test cases might be weak but try to use lazy propagation.....quite challenging! 

Rajat De:
20150703 15:30:13
my AC code fails on


Divyank Duvedi:
20141030 20:58:51
problem is good but test data is weak 

Luis Manuel Dï¿½az Barï¿½n:
20141020 16:43:02
Is TRUE, test cases are too WEAK. I accepted on my first attempt, even though my solution wasn't correct. I put it right and accepted too. Beautiful problem, but too weak 

sanchay:
20140909 00:22:41
Don't put space after 'case %d'....


mark03:
20140824 22:55:23
AC in first! However I think test cases are very weak... 
Added by:  Chen Xiaohong 
Date:  20120711 
Time limit:  1.106s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 