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
Ishan:
20220401 04:43:07
Terrible test casse. The problem is designed to be solved it in O(N*log N + Q*log N) but terrible test cases are allowing O(Q*N*logN) submissions with no lazy propagation what so ever.


luciferhell58:
20200521 13:25:17
i THINK ITS GIVING PROBLEM BECAUSE I AM USING JAVA 

luciferhell58:
20200521 13:22:04
i am getting tle but got this one aceppeted in 300 ms at coding ninjas 

sayan_244:
20200506 15:27:18
I feel they have simply evaluated the codes on the sample test case. They aren't good enough my code is actually not correct as of now >.>


aryan12:
20200302 15:20:59
AC in one go, I don't know how. I was expecting a TLE :) 

dhj:
20200125 13:02:15
To get AC in one go, for an average like me...is super awesome :D 

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

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