Editorial for COCI '14 Contest 3 #5 Stogovi


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Let us imagine a tree of stacks such that each stack from the task corresponds to a path to a certain node in the tree from the root of the tree. Each node will have an integer x assigned to it, excluding the root, which will be assigned zero. Every stack label v will then have a tree node assigned to it, call it f_v. Precisely the number of the node f_v is the number from the top of stack v, and climbing up to the root we would see the whole stack. All the while ignoring the zero at the root, of course.

Let us make sure that this is really possible. At the beginning of the game, we have one empty stack and make a tree with the node zero. While copying stack v and adding a new number we simply add a new node to the tree, assign a number to it and set f_v as its parent. While copying stack v and removing an element from its top, we will output the number in node f_v and assign the parent of f_v to the new stack. It is evident that the tree-like structure is stable after each operation and that all operations are of constant complexity.

We are still left with efficiently answering the query of type c. For starters, let us notice that the numbers placed on stacks are always ascending. In other words, no two tree nodes will have the same number x written in them. So the question "how many of the same numbers are in stacks v and w" is equal to the question "how many of the same nodes, excluding the root, is on the path from the root to f_v and on the path from the root to f_w". All such nodes will be in the first part of the path from the root to f_v/f_w because once the paths part ways, they will never meet again. Therefore, it is sufficient to find the last such node and output how many nodes there are on the path from the root to itself.

Such node is also called the lowest common ancestor in a tree and there are various methods to find it. The most popular solution is "jumps of powers of 2 length" (for more information, consult this link, of the complexity \mathcal O(N \log N) for preprocessing and \mathcal O(\log N) per query.

Additionally, we need to notice that in this task we don't have a complete tree for which we can initially build a jumping table, but it isn't a problem. When adding a new node (the only moment when the tree changes), we will calculate all its jumps in the complexity \mathcal O(\log N) because the jumps of its ancestors have already been calculated.

The total time and memory complexity of this solution is \mathcal O(N \log N).


Comments

There are no comments at the moment.