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
Neeraj Joshi: 2016-04-05 10:11:33

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

Vipul: 2016-02-13 07:52:37

nice problem...

spoj2121: 2015-12-24 20:22:39

easy but lengthy to code...

Last edit: 2015-12-24 20:22:55
karan: 2015-12-19 19:46:41

@Rajat De : Your lazy tree may be getting overwritten.

Sudharsansai: 2015-07-16 20:55:26

Yeah..An easy problem (GOT AC)..But since I rarely implemented Lazy propagation, I wish someone could give me some hard test cases along with the corresponding outputs .
This is my mail id = sudharsan2323@gmail.com
Thanx in advance. Just wish to see whether my solution is absolutely fine... :)

Last edit: 2015-07-16 20:55:58
Jatin Narula: 2015-07-15 22:07:39

test cases might be weak but try to use lazy propagation.....quite challenging!

Rajat De: 2015-07-03 15:30:13

my AC code fails on
1
8 3
0 0 0 0 0 0 0 0
0 5 8 3
1 5 8 1
2 5 6

Divyank Duvedi: 2014-10-30 20:58:51

problem is good but test data is weak

Luis Manuel D�az Bar�n: 2014-10-20 16:43:02

Is TRUE, test cases are too WEAK. I accepted on my first attempt, even though my solution wasn't correct. I put it right and accepted too. Beautiful problem, but too weak

sanchay: 2014-09-09 00:22:41

Don't put space after 'case %d'....
got 3 WA's


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