## 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 64-bit 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
 < Previous 1 2 3 4 5 6 Next > Ishan: 2022-04-01 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. But people who solved in the real expected complexity have learnt a lot. The trick comes in interplay between the two updates, both requiring lazy propagation and how they interplay with each other. luciferhell58: 2020-05-21 13:25:17 i THINK ITS GIVING PROBLEM BECAUSE I AM USING JAVA luciferhell58: 2020-05-21 13:22:04 i am getting tle but got this one aceppeted in 300 ms at coding ninjas sayan_244: 2020-05-06 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 >.> upd:- I think I fixed it now. Last edit: 2020-05-21 06:18:19 aryan12: 2020-03-02 15:20:59 AC in one go, I don't know how. I was expecting a TLE :) dhj: 2020-01-25 13:02:15 To get AC in one go, for an average like me...is super awesome :D hduoc2003: 2019-09-29 05:21:48 I used two segment tree to solve this. Anyone does it better pls tell me!! Thank u very much :> Last edit: 2019-09-29 05:24:13 manishjoshi394: 2019-09-02 13:07:13 AC in one go, very good problem for newbies on Lazy propagation. chirayu_555: 2019-08-24 10:12:12 AC in single go. Do updates properly. Nice problem..!! edygordo: 2019-07-26 19:54:41 2 4 3 1 2 3 4 0 1 4 10 1 1 4 10 2 1 1 4 3 1 2 3 4 1 1 4 10 0 1 4 10 2 1 1 //try this case OUTPUT Should be Case 1: 400 Case 2: 100 // First increase then Replace // First Replace then Increase **(here it's a bit different) //first Increase then increase //first Replace then replace

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