bayram's blog

spoj problem
By bayram, 11 years ago, In English

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

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

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

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

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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)

    → Reply