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
ashishranjan28:
20161103 00:20:18
nice concept of segment tree's lazy propagation 

Ashwani Gautam:
20160925 11:22:01
not worth it if you not using Lazy propagation. 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20160920 13:32:01
Weak test case! my first accepted submission would fail on this "tricky(?)" case:


Willy:
20160728 05:27:50
Don't use http://www.spojtoolkit.com/test/SEGSQRSS for this problem. It has wrong solution. 

liuxueyang:
20160725 11:15:10
I got AC in nonlazy propagation segment tree. I think it's because of the weak test cases. I didn't come up with the solution of lazy propagation segment tree for this problem..


iharsh234:
20160722 11:56:02
Good to go! 

gohanssj9:
20160711 17:17:59
I think Weak testcases. My normal Segment tree passed. 

Vladimir Folunin:
20160610 01:42:45
Please add tests similar to the following one:


Neeraj Joshi:
20160405 10:11:33
first segment tree problem...


Vipul:
20160213 07:52:37
nice problem...

Added by:  Chen Xiaohong 
Date:  20120711 
Time limit:  1.106s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 