Editorial for COCI '06 Contest 4 #6 Ispiti
Submitting an official solution before solving the problem yourself is a bannable offence.
We're looking to design a data structure that holds pairs of numbers and can answer queries of the form "Which pair has both numbers larger than a given pair, but so that the second number differs by as little as possible?". One such data structure is an order-statistic tree (also called tournament tree).
In general, a tournament tree is a complete binary tree whose leaves hold data, while each node higher in the tree holds some desired statistic about the leaf nodes contained in the subtree rooted at that node: for example the smallest number, largest number, sum of numbers etc.
In this problem we'll have the nodes hold the largest number in their subtree. The root node thus holds the largest number of all the leaves, its left child holds the largest in the first half of the sequence etc. The tree is stored in an array so that the children of node
When adding the pair
The tree can tell us the first number larger than the one in leaf node
- Start from the root node (consider the entire tree)
- Repeat:
- If
is not in the subtree rooted at the current node, then none of these nodes are right of so there is no solution in that subtree - If
is in the right subtree, move to that subtree (no nodes in the left subtree are right of ) - Otherwise (
is in the left subtree), if the left subtree contains a number larger than , try to find the first one right of (recursive call) – otherwise, find the leftmost number larger than in the right subtree
- If
It takes some convincing, but working out the cases reveals that the complexity of one query is
One final observation is that the numbers
Comments