Блог пользователя approach

Автор approach, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It sounds like this problem on CSES. CSES problem.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится