Блог пользователя tamir

Автор tamir, 11 лет назад, По-русски

Здравствуйте! Недавно начал изучать декартово дерево . Помогите решить задачу вот эту задачу Декартово дерево.

Спасибо за внимание!

  • Проголосовать: нравится
  • -13
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Отсортируем сначала пары по a.
Найдем пару с максимальным b — это корень дерева, все пары левее ее будут в левом поддереве, остальные — в правом.
Рекурсивно строим левое и правое поддерево тем же алгоритмом.
Чтобы быстро искать максимум можно использовать, например, дерево отрезков.

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Ещё можно явно построить декартово дерево, поочерёдно добавляя в него вершины, прежде отсортировав их по b в порядке уменьшения, чтобы избежать обработки вырожденных деревьев за квадрат.