azatu

Я понял как сдать эту задачу на сабтаски, но не могу понять как сдать ее на фулл при ее ограничениях. Можно подсказку

Nursik

в этом блоге написано решение поэтапно, но я еще слышал, что кто-то сдавал задачу хэшами+small-to-large

Zhabka

На olympiads.bc-pf.org разбор есть

Omerkhan

Помнится, @Yelarys написал хеши с P = 1. Интересно было бы его послушать.

1 ответ

acm

Не знаю о чем речь, но решается задача хэшами так: будем держать хэши на массиве родителей в явном СНМ, то есть в любой момент времени p[v] - действительный предок v. Теперь, когда получаем запрос будем искать бинпоиском первое несовпадение в данных отрезках и мерджить, и так до конца. После мерджа некоторые p[v] поменяются, отразим это и в хешах, будем держать их Фенвиком чтобы не словить TL. Логично, что “полезных” мерджей будет только O(n), значит в целом все суммарно работает за O(nlog^2n).