Это обсуждение публикации https://olympiads.bc-pf.org/informatics/oblast/2022
Я понял как сдать эту задачу на сабтаски, но не могу понять как сдать ее на фулл при ее ограничениях. Можно подсказку
1 лайк
в этом блоге написано решение поэтапно, но я еще слышал, что кто-то сдавал задачу хэшами+small-to-large
1 лайк
На olympiads.bc-pf.org разбор есть
4 лайка
Помнится, @Yelarys написал хеши с P = 1. Интересно было бы его послушать.
1 лайк
Не знаю о чем речь, но решается задача хэшами так: будем держать хэши на массиве родителей в явном СНМ, то есть в любой момент времени p[v] - действительный предок v. Теперь, когда получаем запрос будем искать бинпоиском первое несовпадение в данных отрезках и мерджить, и так до конца. После мерджа некоторые p[v] поменяются, отразим это и в хешах, будем держать их Фенвиком чтобы не словить TL. Логично, что “полезных” мерджей будет только O(n), значит в целом все суммарно работает за O(nlog^2n).