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

SPOJ QTREE4
Автор fsociety00, история, 7 лет назад, По-английски

Need help! I tried to solve SPOJ QTREE4. I used centroid decomposition, but still getting TLE (time limit exceeded). In my code, a query is processed in O(log(n)^2). How can I improve complexity? Any suggestions. Here is my code.

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

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

Auto comment: topic has been updated by fsociety00 (previous revision, new revision, compare).

→ Ответить
»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

You may try a segment tree on the euler tour.You need to understand the euler tour/rmq algorithm for lca first (it can be found here https://en.wikipedia.org/wiki/Lowest_common_ancestor ).Then,build a segment tree holding the maximum value of lev[node1]-2*lev[node2]+lev[node3] where node1 and node3 are at first occurrence,both are white and node2 can be found between them(and is not neccesarily white)- lev[x] denotes the level of node x.Of course,you need to maintain some helping values (e.g maximum of lev[node1]-2*lev[node2]) but I find this a good segment tree exercise.Finally, you get O(logn) per update.

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

    Can you please Elaborate on how to Maintain the Structure. A submission Code would be Extremely Helpful.

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

      This function 'merges' 2 segment nodes(you now the answers for [a;b] in B,for[b+1;c] in C and you get them for [a,c] in A.I'm sorry it isn't very explicit, but i'll try to explain which is every part of the structure.The rest of the segment tree and building euler tour is more of a prequisite and I would PM if requested, but I find the most important part here.

      Code
      → Ответить