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
hduoc2003:
20190929 05:21:48
I used two segment tree to solve this. Anyone does it better pls tell me!! Thank u very much :>


manishjoshi394:
20190902 13:07:13
AC in one go, very good problem for newbies on Lazy propagation. 

chirayu_555:
20190824 10:12:12
AC in single go. Do updates properly. Nice problem..!!


edygordo:
20190726 19:54:41
2


eagleshadow:
20190530 16:31:53
AC in one GO!!! 

msabeer:
20190404 21:59:10
The problem is nice but the dataset is weak. Got AC with mistakes in code. 

pranto_84:
20190401 14:38:09
too weak test case, i got wrong ans with slightly incorrect code first.


itssanat:
20190307 15:04:55
weak test case


ab_biswas09:
20190302 10:50:09
AC in One Go >> Cakewalk 

abhinav_jain02:
20190127 11:40:01
Very very weak test cases.

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