antivenom's blog

Can anybody help me to apply segment tree in it ?
By antivenom, 9 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

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 :)

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

    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

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

      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? :)

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

QSET try this :)

→ Reply