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
yaseenmollik:
20181115 03:34:57
I assume the test case is too weak.. After two hours of trying I have written 204 line of code using segment tree and lazy propagation.. And it got accepted without any freaking tle or wrong answer!! Who knows what happened  _. Btw, great problem..learned a lot.. 

tien0903:
20181113 15:35:44
1 punch and AC with freaking way :D


phoemur:
20181023 18:07:06
Please do not mix up "sum of the squares" with "square of the sums"...


exesharkx:
20181008 09:26:00
AC in one goo! 

magicarp:
20180602 23:48:52
The test cases are extremely weak. Do not do this problem. Try this test case on your AC code and check what it gives by hand:


luka_dzimba911:
20180602 16:13:27
DO NOT USE SPOJ TOOLKIT FOR COMPARISON GIVES WRONG ANSWER FOR MOST OF INPUTS 

vicky_1998:
20180330 18:02:29
It may be easy to find bug in your algorithm , but sometimes you need to see the assignment of space to your containers. Got 4 WA because of this.....I won't repeat it again 

coolio_1:
20180301 10:46:51
Wooohooo!!! AC in 1 go! Nice problem because of the two types of queries. 

tanavya:
20180127 18:57:46
Slightly weak cases. When I checked with a brute force, my accepted code fails when any updated value is 0, because my code just ignores it in the lazy propagation when it does a check like if lazy[i]! Too lazy (heh) to fix it though, but just know, cases are weak!! 

sherlock11:
20180117 14:45:22
weak test case!!!!

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