Treap, RMQ, LCA, Фенвик, корневая
Четверг, 20 марта 2014
ФМЛ 239, Актовый зал
Кодим декартово дерево. По явному, неявному ключу. Функция на отрезке, reverse на отрезке. Дерево отрезков, операции снизу. LCA и RMQ в Offline. LCA двоичными подъемами, подсчет min на пути в дереве. Подсчет min на пути в дереве в offline. Корневая эвристика: отложенные операции, разделение на части, split+rebuild.
Подробнее: plan & code