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

Автор Hosen_ba, история, 15 месяцев назад, По-английски

Hi, Codeforces.

Recently I have been thinking of the following task:

You are given a tree with $$$N$$$ vertices, each vertex $$$v$$$ has a value $$$a_v$$$ written on it, and you have to process following query ONLINE. given two vertices $$$u$$$ and $$$v$$$, you have to output the MEX of the values on the path from $$$u$$$ to $$$v$$$. The values are not necessarily distinct.

constrains: $$$N$$$<=1e5

If anyone can share any ideas, I will be extremely grateful.

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

»
15 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Really interesting problem!

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

Interesting task!

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

I think you can use heavy-light decomposition and store segment trees for count of elements and existence of elements. Then use binary search to find the answer. Probably it's like $$$O(\log n \log^2 M)$$$ though (where $$$M$$$ is $$$max(a)$$$).

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    Thank you ,but Could you explain this in more details pls?

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Ok, sorry, upon further thought, that won't work because I can't think of any simple way to merge the existence of elements...

      What I had in my mind, is that you can find mex by binary searching upon the element (say $$$i$$$) and then checking if there are exactly $$$i$$$ distinct elements $$$<i$$$. That's why I needed existence, and for existence, I just have to check if there are non-zero occurrences of the element. But I can't merge existences... it's like merging two sets.

      Perhaps, if $$$max(a)$$$ is small, we can do it using bitsets?

»
15 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Nice one!! Excited to see the solution

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

There's a simple solution if $$$a$$$ is a permutation: simply build HLD and then query for the minimum in all nodes that do not lie on the path. One, but not the only way to do that would be to use lazy propagation and fill the path with $$$\inf$$$, then query for the minimum on the whole tree, then reset the values back to normal ones (store a copy of the segment tree in an array and use lazy flags to roll back the changes).

If the numbers are big I don't think there's a solution since the only way to do this for a regular array heavily relies on the fact that you query segments, you could reduce the problem by flattening the tree but there would be conflicts with LCA not being considered.