Разобрался в сабже, хочу найти задачек по теме. Беглый поиск дал немного результатов. Накидайте, пожалуйста, ссылок)
Что уже нашел я:
http://acm.timus.ru/problem.aspx?space=1&num=1553
Что есть в комментариях:
http://www.usaco.org/index.php?page=viewproblem2&cpid=102
http://www.codechef.com/problems/QTREE
http://codeforces.net/contest/226/problem/E
P.S. Буду обновлять список ссылок по мере поступления
Внизу этой статьи 4 задачи
Вроде как все задачи на SPOJ, идентификатор которых начинается на QTREE и затем идет цифра, решаются с помощью этой структуры данных.
Неправда. Только QTREE.
Но ведь емакс дает ссылку на QTREE3 :)
Она решается двоичным подъемом. Решать ее с помощью HLD — лишняя трата сил и времени.
heavy-light. С персистентными деревьями отрезков внутри ;)
Можно и без этого (см. второе решение в разборе), но первым в голову, по-моему, именно это решение в голову приходит. Другое придумывается сложнее, зато пишется намного проще.
Бывает и персистентная HLD. Специально для любителей немного думать и много писать.
А это делается иначе чем "реализуем обычный хеви-лайт, используя для всего персистентный массив" или запихиванием всего в персистентное декартово дерево?
Там кроме этого еще надо хранить дерево персистентных деревьев последних модификаций. Но это неочевидно до тех пор, пока не начнешь писать решение и не получишь WA.
http://www.codechef.com/problems/QTREE
Grass Planting (USACO DEC11)
В последней не обязательно использовать HLD, но с HLD вроде бы как очевидное решение получается.
Можно решить хеви-лайтом