## 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 Next > vicky_1998: 2018-03-30 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: 2018-03-01 10:46:51 Wooohooo!!! AC in 1 go! Nice problem because of the two types of queries. tanavya: 2018-01-27 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: 2018-01-17 14:45:22 weak test case!!!! after getting AC with simple segment tree try to use lazy tu3297: 2017-11-03 21:13:45 IT +LAZY shubham: 2017-06-20 15:56:52 AC in one go :) lord_poseidon: 2017-06-04 15:32:58 ac in one go mddaud001: 2017-05-21 21:35:25 AC:- SEGMENT TREE + LAZY PROPOGATION Written code in 50 minute Too Bad -:- shamiul93: 2017-04-29 22:05:16 easy one.poor test cases. -_- Last edit: 2017-04-29 22:05:44 harshit_walia: 2017-02-12 13:49:11 my 2nd on segment + lazy

 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