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

Помощь с задачей Happy Painting.
Автор robotdron, 12 лет назад, По-русски

Всем привет. Нужна помощь в решении задачи: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=66&page=show_problem&problem=3145 Среди тех методов, которые напрашиваются: heavy-light декомпозиция с использованием неявных декартовых деревьев (чтобы можно было выполнять запросы первого типа — переподвешивание, с соответствующим перестроением декомпозиции (тяжелость-легкость ребер может измениться только на пути от переподвешиваемой вершины до корня её дерева), неявные декартовы деревья как раз нужны для отрезания и приклеивания отрезков друг к другу в вершинах до корня). Но грубая оценка для сложности такого переподвешивания O(n*log(n)). Any ideas? Спасибо.

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

»
12 лет назад, # |
← Rev. 3   Проголосовать: нравится +12 Проголосовать: не нравится

С первого взгляда — в явном виде Linking-Cutting Trees. Почти то, что вы сказали, но heavy-light перестраивается по ходу (похоже на splay-дерево). Сделали операцию с вершиной — сделали так, чтобы весь путь от неё до корня стал одним деревом (возможно, порезав старые).

Утверждается, что это будет работать за O(log) операций с деревьями (т.е. O(log2) в сумме). Если написать внутрь splay-дерево, то будет почему-то (а PavelKunyavskiy даже умеет доказывать) работать за O(log) в сумме.

Сейчас это считается очень сложной структурой данных. Возможно, есть решение проще.

UPD: верю, что можно проще — у нас не "переворачиваются" поддеревья. Возможно, двоичными подъёмами или как-то еще. Сейчас времени чуть подумать и расписать, увы, нет. А LCT увидел, так как это очень общая структура.

→ Ответить