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