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

Can anybody help me to apply segment tree in it ?
Автор antivenom, 9 лет назад, По-английски

Can anybody help me how to solve this question using segment tree.I am not getting what values should I maintain for nodes in order to get final result and how to merge them back to get parent of the childres etc.if possible please provide source code also.Thanks a lot

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

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

What you need to keep in a node is the amount of numbers in the interval that give remainders 0,1,2 respectively when divided by 3. Let those numbers be a0,a1,a2. The answer for a queried node will be a0. If a node needs to be updated, then we can simply shift the sequence a0,a1,a2 one position to the right. That is, it will become a2,a0,a1. Here is my code: http://ideone.com/rle8iQ :)

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    hello Sir :) Thanks for answering my question.I request you to add some comments in the code.I am facing some problem understanding it properly.If you could do this it will be great help to me thanks alot

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Which parts you didn't understand, I will try to explain them? I ask because I don't know what comments to add, it is just lazy propagation with the above idea. Or maybe you didn't understand my explanation? :)

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

QSET try this :)

→ Ответить