I've been struggling with this problem for days now, and there isn't any decent discussion / editorial available on the internet as well. Any pointers / hints for the solution?

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | Um_nik | 3544 |

3 | maroonrk | 3431 |

4 | tourist | 3409 |

5 | apiadu | 3397 |

6 | 300iq | 3317 |

7 | ecnerwala | 3260 |

7 | Benq | 3260 |

9 | LHiC | 3229 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 193 |

2 | antontrygubO_o | 191 |

3 | vovuh | 178 |

4 | pikmike | 177 |

5 | tourist | 166 |

6 | Um_nik | 165 |

7 | McDic | 164 |

8 | ko_osaga | 163 |

9 | Radewoosh | 162 |

10 | 300iq | 156 |

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2020 22:49:36 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Do you know smth about HLD? You can read about it here : http://blog.anudeep2011.com/heavy-light-decomposition/ . It's classic HLD BUT: your data structure must can calculate number of distinct number on the interval. Persistent segment tree can help you with it. http://codeforces.com/blog/entry/8962 — in this blog you can find how to calculate number of distinct numbers on the interval. Solution: HLD + ( Persistent segment tree or Fenwick Tree ) HLD + Fenwick Tree must be much easier to implement.

Yes I know about HLD. After decomposition when we get the chains, we lay them side-by-side in our 'base array' (over which we maintain our required data-structure). But I'm getting stuck at the query part? Each path in the query can be broken down into some chains so we've to query over each chain and combine the results to get the number of distinct numbers. How to do this? Any specifics will be greatly appreciated.

EDIT : In other words, we are not asked to find the distinct numbers in a contiguous segment but the number of distinct numbers over a collection of disjoint contiguous segments.

Not sure if it's possible with HLD, but here is how I solved it.

First we will solve the 1D version of this problem using what is sometimes called Mo's algorithm. Sort all queries (l,r) by (l/SQRTN, r). This basically puts each query into a block of size SQRTN based on its left index and then within each block queries are sorted by right index. To get from one query to the next query, we will have to add/remove some numbers on the left and add/remove some numbers to the right. If we keep track of the counts of each number, we can update the number of distinct numbers after adding/removing a single number in constant time. Since within each block the left indices differ by at most SQRTN and the right index is always moving right, overall this runs in O(M SQRTN). (There is a faster way of solving this problem but that idea doesn't seem to translate well onto a tree?)

How do we use this to solve the problem on a tree? The standard method of linearizing a tree by using its dfs traversal doesn't work, as nodes that are O(1) apart in the traversal can be O(N) apart in the actual tree. We want nodes that are O(1) apart in our traversal to also be O(1) apart in the tree. To do this, we will slightly modify the standard dfs traversal, by adding nodes at even depth to our traversal as we go down, and nodes at odd depth to our traversal as we go up, kind of "hopping" down and up the tree. This ensures that nodes right next to each other in the traversal are at most 3 nodes apart in the actual tree. So we can sort queries using our traversal, and to get from one query to the next, we will have to add/remove nodes in the actual tree. Since within each block the left nodes are at most SQRTN distance apart and the right node essentially traverses the tree, overall this runs in O(M SQRTN).

Wow, that's really clever :). I was requested by shelob to take a look at that problem, but I couldn't solve it. What is funny is that I came up with generalization of Mo's algorithm to trees something like ~3 years ago :D. My way was to divide the tree to subtrees of depth (that is easy by greedy algo) and then we can easily answer queries if we group points belonging to the same subtree, however it's not that easy to implement. As I think about your solution this seems nicer, however it looks like it could be simplified even further. In standard way of linearizing tree we do something like

however we can do something like

and we achieve the same goal without adding any more nodes, just adding one line "d++" :). Some numbers will be missing, but that does not break anything.

as I understood yzyz's solution he's not adding more nodes too, what is doing is like

also could you explain how is your way guarantee O(M sqrt N) although there can still adjacent nodes can still be O(N) far from each other

UPD:ok I got how, it's like Euler tour :)Ah, yes, that was already pretty late, so I didn't clearly get yzyz's idea.

Btw in my version I think that

abs(pre[u] -pre[v]) ≥dis(u,v) is satisfied and that should be sufficient, right?yes I got that thanks

An easier way to word it is that a contiguous portion of our ordering must be a connected component in the tree.

Can you explain how you make transition from one query to the next?

if not too much trouble could you please elaborate your tour with an example tree and show how the linear representation would look like ??

Judge gives runtime error please see my code i have used mo's algorithm i could not identify error thanks in advance please see https://ideone.com/MG3XbK

Input has multiple test cases. It is not mentioned in the problem statement! You need to take input till EOF :|

Can't agree with that. I have got AC and just resubmitted my solution (still AC) which doesn't handle multiple cases.

http://codeforces.com/blog/entry/43230

The code given here is handling multiple case.. I am not sure.

Man, "the code could handle multiple cases if needed" doesn't mean that the problem has multiple cases in a single test file.

Can you please share your code?

Mo on tree

In the HLD tutorial here. I saw the suggested problems include COT2.

So I wonder if anybody solved it with HLD. If yes, can you give me a detailed solution for HLD? The point of finding "the number of distinct numbers over a collection of disjoint contiguous segments.".

Thanks a lot <3 <3.

I solved it using MO's algorithm. Here is the link:

https://github.com/saurabhshadow/Sport-Programming/blob/master/Practice/MO's%20Algo/COT2.cpp

You forgot to add Link saurabhshadow

I don't know how to put the clickable link, so I have given the link.