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
Ishan:
2022-04-01 04:43:07
Terrible test casse. The problem is designed to be solved it in O(N*log N + Q*log N) but terrible test cases are allowing O(Q*N*logN) submissions with no lazy propagation what so ever.
|
|
luciferhell58:
2020-05-21 13:25:17
i THINK ITS GIVING PROBLEM BECAUSE I AM USING JAVA |
|
luciferhell58:
2020-05-21 13:22:04
i am getting tle but got this one aceppeted in 300 ms at coding ninjas |
|
sayan_244:
2020-05-06 15:27:18
I feel they have simply evaluated the codes on the sample test case. They aren't good enough my code is actually not correct as of now >.>
|
|
aryan12:
2020-03-02 15:20:59
AC in one go, I don't know how. I was expecting a TLE :) |
|
dhj:
2020-01-25 13:02:15
To get AC in one go, for an average like me...is super awesome :D |
|
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 :>
|
|
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
|
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 |