Розбір

Група 1. Переберемо всі можливі множини $S$ та перевіримо чи можемо відсортувати перестановку для кожної з множин.

Група 2. Розмір мінімальної множини, коли $n\le 32$ не перевищує $5$ (якщо обрати $S=\{1,2,4,8,16\}$, то нескладно відсортувати будь-яку перестановку розміром до $32$), тому можна перебирати лише множини розміру до $4$ та перевіряти чи можна відсортувати перестановку.

Група 3. Є три можливі випадки в залежності від мінімального $mi{n}_S$ розміру доброї множини $S$ у цьому випадку:

1. $mi{n}_S=0\leftrightarrow p_i=i$ для всіх $0\le i<n$;

2. $mi{n}_S=1\leftrightarrow \exists i:i\ne p_i$ та $\exists x:\forall i(i=p_i\vee i\oplus p_i=x)$;

3. Інакше $mi{n}_S=2$.

За допомогою std::map можна підтримувати множину всіх значень $i\oplus p_i$ і перевіряти скільки існує унікальних ненульових значень $i\oplus p_i$.

Група 4. Нехай в нас є деяка множина $S$, за допомогою якої ми можемо відсортувати нашу перестановки використовуючи операції з умови.

Розгянемо елемент, що стояв на позиції $i$ у початковій перестановці. Очевидно, що у тотожній перестановці він знаходиться на позиції $p_i$. Розглянемо послідовність позицій на яких побував елемент перестановки зі значенням $p_i$ перед тим як перейти на фінальну позицію:

при чому $c_{i+1}=c_i\oplus x_i$, де $x_i\in S$ для таких $i$, що $0\le i<k$.

Виразимо $c_k$ через $c_0$: $c_k=c_0\oplus x_0\oplus x_1\oplus \dots \oplus x_{k-1}$. Тоді маємо, що

Тобто маємо, що щоб переставити елемент зі значенням $p_i$ на свою позицію необхідно, щоб ксорами елементів множини $S$ можна було представити число $i\oplus p_i$ для кожного $i$: $0\le i<n$.

Пригадаємо XOR базис. XOR базис — це мінімальний набір чисел, які можуть представляти будь-яке число заданої множини за допомогою комбінацій XOR. Детальніше можна дізнатися тут.

Нескладно довести, що якщо взяти $S$ як XOR базис чисел $i\oplus p_i$ побудований алгоритмом наведеним нижче, то це і буде одна з множин мінімального розміру, якою можна відсортувати задану перестановку.

vector <int> basis;

void add (int x) {
    for (int i : basis) {
        x = min(x, x ^ i);
    }
    if (x) {
        for (int &i : basis) {
            i = min(i, i ^ x);
        }
        basis.push_back(x);
    }
}

Тоді відповіддю на кожен запит є розмір XOR базису побудованого на числах $i\oplus p_i$.

Тоді після кожного запиту можемо за $O(n\cdot logn)$ порахувати розмір XOR базису та вивести його. Складність розв'язку: $O(q\cdot n\cdot logn)$.

Група 5. За домогою дерева відрізків можна підримувати XOR базис масиву за $O(lo{g}^3(n))$ на запит. В кожній вершині будемо зберігати XOR базис чисел $i\oplus p_i$ за які відповідає відповідний сегмент дерева відрізків.

Об'єднувати два базиси можна в лоб за $O(lo{g}^2(n))$. Тоді операція оновлення буде працювати за $O(lo{g}^3(n))$.

Група 6. Коли $\beta =0$, то ми знаємо всі запити наперед. До XOR базису ми можемо додавати елементи. Але, на жаль, не можемо видаляти. Маючи все це можемо використати цю техніку, яка дозволяє видаляти із структури, в яку можемо додавати, якщо запити дано наперед.

Група 7.

Як підтримувати XOR базис в онлайні за $O({\log }^{2}n)$ на запит можна дізнатися за посиланням.