approach's blog

Help needed in range based query problem.

By approach, history, 4 years ago, In English

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

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It sounds like this problem on CSES. CSES problem.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

actually, the answer to this problem was that for each city number of statues destroyed was Σ (i-L+1) where i is city number

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://www.codechef.com/viewsolution/40958260

check it out

→ Reply