Прочитал отличный цикл статей от Skiminok о дерамиде.
Хотелось бы применить полученные знания на практике.
Сам могу указать две задачи с тимуса: War Games 2 и Battle with You-Know-Who. Но в них используются лишь относительно простые операции, хотелось бы чего-нибудь повеселее.
http://acm.timus.ru/problem.aspx?space=1&num=1469
http://acm.timus.ru/problem.aspx?space=1&num=1839
В Кормене есть разбор. В кратце так:
Сортируем все точки концов и начал отрезков по x. Потом сканлайном по этим точкам строится множество отрезков, сравнение - у кого точка пересечения со сканлайном ниже. Если точка открывает наш отрезок - то смотрятся непосредственно следующий и предыдущий отрезки в множестве, если наш пересекается с одним из них, то ответ найден. Ну и добавить отрезок надо. Если точка закрывает наш отрезок, то проверяется пересечение следующего и предыдущего во множестве, и отрезок удаляется. Собственно тут всплывает много операций: add, delete, prev, next, так что подходит сбаллансированое деревое, например treap.
Очень приятная задача. Из раздела единственная, над которой пришлось думать.
Решил сначала SQRT-декомпозицией - так мне почему-то проще рассуждать было, затем переписал на дерамиду. С дерамидой получилось намного короче и красивее. Прямо проникся мощью дерамиды по неявному ключу.
"нужно будет хранить сумму в блоке на чётных/нечётных позициях" - не совсем верно.
В любом случае, ответ в первой правке.
http://acm.timus.ru/problem.aspx?space=1&num=1521
UPD: Насколько вспомнил, есть ещё дуча и курево.
А как это нормально фенвиком делать?
Я вижу только за квадрат логарифма - бинпоиском искать место с нужной суммой.
Фенвиком можно за O(1) находить сумму ненулевых элементов на отрезке от [1..R]. А двоичным поиском искать это R - и того O(LogN) на запрос.Я ещё понимаю, как приспособить сюда что-то похожее на двоичные подъёмы, чтобы в сумме за O(log) работало.
.
Если у кого есть построение на Паскале дерамиды по явному ключу можно попросить код посмотреть. Сам написал, но не во всех случаях верно строит. Хочу попробовать понять правильное решение.