I know how to increase values in an array from 'L' to 'R' by a constant no.
- first value by 1
- second value by 1
- third value by 1
but unable to figure out how to increment value like ..
- first value by 1
- second value by 2
- third value by 3 and so.....
Problem was :: Angry Cyborg
I tried few approaches like decreasing R + 1th element by R — L + 1 and so but they didn't seem to work.
I am stuck in this question, can u please provide any hint. You have my thanks !!
It sounds like this problem on CSES. CSES problem.
actually, the answer to this problem was that for each city number of statues destroyed was Σ (i-L+1) where i is city number
For Query (L,R) increase A[L] by 1, A[R+1] by -(R-L+2) and A[R+2] by (R-L+1). After processing all queries take prefix sums twice.
this can be solved using segment tree and lazy propagation.
store three values for each node of your segment tree:
- $$$d_i$$$ : the number of queries that applied to $$$i_{th}$$$ node.
- $$$v_i$$$ : the number that must be added to the leftmost element of the $$$i_{th}$$$ node.
- $$$s_i$$$ : sum of elements of $$$i_{th}$$$ node.
shifting first two values to deeper nodes is simple, also you can update the value of $$$s_i$$$ using the other two values.
https://www.codechef.com/viewsolution/40958260
check it out