Изменения

Отсортируем парочки <tex>(x_i, y_i)</tex> по убыванию <tex>x_i</tex> и положим их в очередь. Сперва достанем из очереди первый 2 элемента и сольем их в дерево и положим в конец очереди, затем сделаем то же самое со следующими двумя и т.д. Таким образом, мы сольем сначала n деревьев размера 1, затем <tex>\dfrac{n}{2}</2 tex> деревьев размера 2 и так далее. При этом на каждый круг уменьшение размера очереди в два раза мы будем трать тратить суммарно <tex>O(n)</tex> времяна слияния, а всего кругов таких уменьшений будет <tex>\log n</tex> (т.к. с каждым кругом количество элементов в очереди будет уменьшаться в два раза). Значит полное время работы алгоритма будет <tex>O(n\log n)</tex>.