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

Автор bayram, 11 лет назад, По-английски

I try use heavy-light decomposition to solve problem http://www.spoj.pl/problems/COT/. But I can't do it. Please help to solve that problem. Thanks for your helping! :)

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

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

I can solve this problem in O(N * Log(N)^2). We have to use heavy-light decomposition + persistent segment trees. For each chain of decomposition we have to build segment trees t[i] where t[i] is a tree for first i vertices of chain from top to bottom. At first step we can transform all numbers into numbers from 1 to n. Then build a "start" tree a[i] = 0, for i 1..n . To add a vertice with number X to a tree we just increase value at X. i.e. a[X]++; To answer a query for two vertices X and Y we have to find their LCA Z. Then find about O(log(N)) trees on the way from Z to X and from Z to Y. It is easy to find k-th element of a tree merged from these ones.

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

I think u can solve it in O(n*log^3(n)). Use binary search with heavy light. Save all numbers in sorted order for each stage in segment tree. It is quite easy to write. But i dont know will it be good for TL.

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

I found someone's solutions which gets accepted. But I didn't understand the code. Here is link.

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

    It's NlogN solution. It's also uses Persistent segment tree. Let's build a tree described above in my solution, but for each vertice. Tree for a fixed vertice x contains all values on the way from root to this vertice. tree T(x, y) — tree for the way from x to y is T(x, z) + T(y, z) — 2 * T(root, z), where z = LCA(x, y)