Hosen_ba's blog

[HELP] Online mex queries
By Hosen_ba, history, 12 months ago, In English

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.

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

»
12 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Really interesting problem!

→ Reply
»
12 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Interesting task!

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

interesting !!

→ Reply
»
12 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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)$$$).

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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?

      → Reply
»
12 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Nice one!! Excited to see the solution

→ Reply
»
12 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

→ Reply