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
harshit_walia: 2017-02-12 13:49:11

my 2nd on segment + lazy

ashishranjan28: 2016-11-03 00:20:18

nice concept of segment tree's lazy propagation

Ashwani Gautam: 2016-09-25 11:22:01

not worth it if you do not using Lazy propagation.

Last edit: 2017-02-28 14:47:16
(Tjandra Satria Gunawan)(曾毅昆): 2016-09-20 13:32:01

Weak test case! my first accepted submission would fail on this "tricky(?)" case:
1
6 2
1 2 3 4 5 6
1 2 5 -3
2 3 4

Willy: 2016-07-28 05:27:50

Don't use http://www.spojtoolkit.com/test/SEGSQRSS for this problem. It has wrong solution.

liuxueyang: 2016-07-25 11:15:10

I got AC in non-lazy propagation segment tree. I think it's because of the weak test cases. I didn't come up with the solution of lazy propagation segment tree for this problem..
But how to use lazy propagation in this problem? any idea?

Last edit: 2016-07-25 11:16:50
iharsh234: 2016-07-22 11:56:02

Good to go!

gohanssj9: 2016-07-11 17:17:59

I think Weak testcases. My normal Segment tree passed.

Vladimir Folunin: 2016-06-10 01:42:45

Please add tests similar to the following one:
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

Last edit: 2016-06-10 01:43:37
Neeraj Joshi: 2016-04-05 10:11:33

first segment tree problem...
without lazy AC... :)


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