Задача №2781. Декартово дерево
Вам даны пары чисел \((a_i, b_i)\), Вам необходимо построить декартово дерево, такое что \(i\)-ая вершина имеет ключи \((a_i, b_i)\), вершины с ключом \(a_i\) образуют бинарное дерево поиска, а вершины с ключом \(b_i\) образуют кучу на минимум.
В первой строке записано число \(N\) — количество пар. Далее следует \(N\) (\(1 \le N \le 50\,000\)) пар \((a_i, b_i)\). Для всех пар \(\lvert a_i\rvert, \lvert b_i \rvert \le 30\,000\). \(a_i \ne a_j\) и \(b_i \neq b_j\) для всех \(i \ne j\).
Если декартово дерево с таким набором ключей построить возможно, выведите в первой строке YES, в противном случае выведите NO. В случае ответа YES, выведите \(N\) строк, каждая из которых должна описывать вершину. Описание вершины состоит из трёх чисел: номер предка, номер левого сына и номер правого сына. Если у вершины отсутствует предок или какой-либо из сыновей, то выводите на его месте число 0.
Если подходящих деревьев несколько, выведите любое.
7 5 4 2 2 3 9 0 5 1 3 6 6 4 11
YES 2 3 6 0 5 1 1 0 7 5 0 0 2 4 0 1 0 0 3 0 0