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
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

eagleshadow: 2019-05-30 16:31:53

AC in one GO!!!

msabeer: 2019-04-04 21:59:10

The problem is nice but the dataset is weak. Got AC with mistakes in code.

pranto_84: 2019-04-01 14:38:09

too weak test case, i got wrong ans with slightly incorrect code first.
Thanks magicarp for your test case :)

itssanat: 2019-03-07 15:04:55

weak test case

ab_biswas09: 2019-03-02 10:50:09

AC in One Go >> Cakewalk

abhinav_jain02: 2019-01-27 11:40:01

Very very weak test cases.
Got AC even with slightly incorrect code at first


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