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

PROBLEM IN UNDERSTANDING PROPAGATING TREE(383C)
Автор javacoder1, история, 9 лет назад, По-английски

I am having problem understanding how we are utilising Binary Indexed tree to solve the problem.The DFS part is clear as well as the notion of levels. But i am unable to understand how BIT is used. http://mirror.codeforces.com/contest/383/problem/C link.

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

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

i solved it with segment tree . 1. find starting time and finishing time and also depth of each vertex with a dfs

  1. in segment tree interval of each vertex v with we do operation on it is [str[v] , fin[v]] because all of children of v have a starting time greater than v and finishing time less than v

  2. build 2 segment trees one for the ones with even depth and one for odd depth now when you r updating a vertex v you change intervals of one segment tree by +val and the other -val (just compare their depth mod 2)

  3. now for get queries just go throught every segment with vertex v in it and add it's value to answer !

check my code if u want (it's ugly :) ) http://mirror.codeforces.com/contest/383/submission/13809240

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

    It would be much better if anyone could explain it with binary indexed tree.

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

    Some nodes b/w [str[v], fin[v]] will have +val, while remaining nodes will have -val . Why are we adding +val on whole range [str(v) , fin[v]] ?

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

      http://mirror.codeforces.com/contest/383/submission/15232082

      check this solution. Here we are maintaining the notion of levels. Suppose the level is odd we are adding -val to all the children and if the level is even we are adding +val.But we have to make the children of let's say even level nodes -val we are taking care of this when we are taking the query look , we have taken negative sign which makes this +val appear as -val. Suppose now we have performed this query on a node which has a subtree of depth 6 and this node is at even level.all nodes at odd and even level have a value of +val.Another query at it's children which is at odd level make all the children of this child node achieve value of -val1 .The grandchild of node has value of +val-val1 which is what we desire and this node is at even level so we are simply adding this value at the query with the initail value.the child of this grandchild has too the value +val-val1 but we desire -val+val1 which is taken care in query by taking the negative sign in case of odd levels and adding it to the initial value.By this you can notice that the problem is symmetric if during update at odd levels we do +val then during query we also do +val and so for even levels we do -val in update and query. As you can see single BIT is enough but you can also use two BIT's one for updating even levels with +val (bit1) and one for updating odd levels with -val (bit2).on query at odd level we do -(bit1 + bit2) and at even level we do +(bit1+bit2)

      → Ответить