Автор та розробник: Святослав Бідзіля
Спробуємо розв'язати задачу, якщо в нас вже множина чисел $$$S$$$ з піддерева і нам потрібно знайти $$$k$$$-е число з множини всіх можливих XOR-сум підмножин.
У випадку, якщо всі числа є степеню двійки можна помітити, що якщо число є в наборі, то ми можемо або додати його у відповідь, або ні. Так можна зробити з кожним бітом, тому всього буде в множині $$$2^{|S|}$$$ чисел. Побудувати $$$k$$$-е число можна жадібно - будемо йти з найбільших чисел до найменших. Якщо ми можемо не ставити якийсь біт (чисел з цим бітом не встановленим $$$\geq k$$$), то ми не будемо його ставити. Інакше, поставимо цей біт і зменшимо $$$k$$$ на кількість чисел, в яких цей біт не встановлений.
Для розв'язання задачі в загальному вигляді потрібно розглянути числа, як набір векторів над полем $$$Z_2$$$. Тоді, xor двох чисел - це додавання цих векторів. Тому, для знаходження всіх можливих xor-ів підмножин, можна побудувати базис векторів, які представляють числа з множини $$$S$$$ і подібно до рішення в минулому пункті жадібно встановлювати біти від більшого до меншого. Побудова базису може бути реалізована за $$$O(\log ^3 A)$$$(Може бути пришвидшено в 32 рази використовуючи бітові операції на числах), а пошук $$$k$$$-го елементу в побудованому базисі - за $$$O(log A)$$$.
Тепер, повернемося до оригінальної задачі. Для перших трьох підгруп було достатньо знайти всю множину чисел пошуком вглибину, а далі використати розв'язок з першої частини.
Блок 1 Будь-який повний перебір за $$$O((n + q) 2 ^ n)$$$ проходив цей блок.
Блок 2-3 Блок проходився якщо перераховувати базиси для всіх вершин за $$$O(n)$$$, або знаходити кожний раз заново.
Блок 4 Можна реалізувати задачу для множини чисел, а не дерева.
Блок 5 Якщо в підгрупі немає запитів на зміну числа, то можемо передрахувати всі базиси для кожної вершини дерева - базис вершини це просто базис чисел з базисів її дітей. Це можна порахувати за $$$O(n \log^2 A)$$$, а далі відповідати за запити за $$$O(\log A)$$$.
Блок 6 Блок вирішувався простішим варіантом базису, достатньо було перевірити наявність потрібного біта в піддереві.
Блок 7 У загальному випадку, можемо звернутися до техніки Ейлерового обходу дерева. Побудуємо за Ейлеровим обходом дерева дерево відрізків, де в кожній вершині буде зберігатися XOR базис її підвідрізка. Для мерджа двох вершин додамо вектори одного базису в інший. Піддерево кожної вершини тепер буде цілісним відрізком на Ейлеровому обході, а отже запит базису на піддереві зводиться до одного запиту до дерева відрізків, а запит зміни числа - до одиничної заміни в дереві відрізків. Реалізація такого дерева відрізків працює за $$$O( \log^2 A \log n)$$$ на запит, тому все рішення працює за $$$O((n + q) \log ^2A \log n)$$$.