Информатика → Областная → 2022 | BeyondOlympiads

Обсуждаем олимпиады
6

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