Запити краси перестановки#11732

Запити краси перестановки (Розбір)

Автор задачі:	Костянтин Денисов
Задачу пiдготував:	Костянтин Денисов, Максим Шведченко
Розбiр написав:	Костянтин Денисов

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

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

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

$mi n_{S} = 0 \leftrightarrow p_{i} = i$ min_S=0 \leftrightarrow p_i=i для всіх $0 \leq i < n$ 0 \le i < n;
$mi n_{S} = 1 \leftrightarrow \exists i : i \neq = p_{i}$ min_S=1 \leftrightarrow \exist i: i \neq p_i та $\exists x : \forall i (i = p_{i} \lor i \oplus p_{i} = x)$ \exist x: \forall i (i = p_i \lor i \oplus p_i = x);
Інакше $mi n_{S} = 2$ min_S=2.

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

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

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

$c_{0} = i \to c_{1} \to c_{2} \to \dots \to c_{k - 1} \to c_{k} = p_{i}$ c_0=i \rightarrow c_1 \rightarrow c_2 \rightarrow \ldots \rightarrow c_{k-1} \rightarrow c_k=p_i.

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

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

$x_{0} \oplus x_{1} \oplus \dots \oplus x_{k - 1} = c_{k} \oplus c_{0} = i \oplus p_{i}$ x_0 \oplus x_1 \oplus \ldots \oplus x_{k-1}=c_k \oplus c_0 = i \oplus p_i.

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

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

Нескладно довести, що якщо взяти $S$ як XOR базис чисел $i \oplus p_{i}$ 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}$ i \oplus p_i.

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

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

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

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

Група 7.

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