Этот блог основан на задаче 1591D - Ещё одна задача на сортировку, надеюсь вам он понравится.

Базовые понятия

Для начала, разберемся в базовых понятиях, вы можете пропустить эту секцию, если все знаете.

Четность перестановки $$$p$$$ это четность количества инверсий в ней. Инверсия это пара $$$(i, j)$$$ такая, что $$$i < j, p_i > p_j$$$.

Композиция перестановок определяется так $$$(f \circ g)_x = f_{g_x}$$$, мы сначала применяем $$$g$$$, затем $$$f$$$.

Цикл это перестановка, где некоторые индексы циклически сдвинуты, например $$$p = \begin{pmatrix}1 & 5 & 2 & 4 & 3\end{pmatrix}$$$ это цикл $$$\begin{pmatrix}2 & 3 & 5\end{pmatrix}$$$.

Теорема. Любая перестановка это композиция непересекающихся циклов.

Доказательство. Посмотрим на граф с вершинами от $$$1$$$ до $$$n$$$, и ребрами $$$i \to p_i$$$ для всех $$$i$$$. Поскольку $$$p$$$ перестановка, входящая и исходящая степень любой вершины равна 1, значит наш граф это набор циклов, что и требовалось.

Лемма. Применяя транспозицию(меняя два элемента местами) мы меняем четность перестановки.

Эта лемма очень важна, поэтому остается в качестве упражнения читателю

Факт. Четность $$$(f \circ g)$$$ равна сумме четностей $$$f$$$ и $$$g$$$.

Доказательство. Применение транспозиции меняет четность, поэтому если $$$f$$$ представляется в виде $$$k$$$ транспозиции, то четность $$$k$$$ это четность $$$f$$$. Пусть $$$f$$$ представляется $$$k$$$ транспозициями, а $$$g$$$ представляется $$$m$$$ транспозициями, тогда $$$f \circ g$$$ может быть представлена как $$$k + m$$$ транспозиций, но четность $$$f \circ g$$$ это четность $$$k + m$$$, что в свою очередь является суммой чётностей $$$f$$$ и $$$g$$$, ЧТД.

Подсчёт числа инверсий и четности перестановки

Существует очень много способов посчитать количество инверсий за $$$O(n \log n)$$$.

Однако, существует простой способ посчитать четность перестановки, не считая напрямую количество инверсий.

Теорема. Перестановка представляется в виде композиции 3-циклов тогда и только тогда, когда она чётная.

Доказательство. 3-цикл чётный, поэтому композиция 3-циклов тоже четная. Осталось только доказать, что для четных перестановок такое представление существует.

Попробуем построить его итеративно, начиная с тождественной перестановки, последовательно применяя 3-циклы. На $$$i$$$-ой итерации мы предполагаем, что первые $$$i - 1$$$ элементов уже стоят на месте, и мы пытаемся поставить $$$i$$$-ый. Если $$$i$$$-ый элемент не на месте, то пусть в текущей перестановке он находится на месте $$$j$$$. Тогда $$$j > i$$$, и давайте применим цикл $$$n \to j \to i$$$, а если $$$j = n$$$, то $$$n - 1 \to j \to i$$$. Таким образом мы можем поставить на место $$$i$$$-ый элемент, и не нарушить расположение предыдущих.

Так мы можем сделать $$$n - 2$$$ шагов. Далее возможны две ситуации

1. Последние два элемента на месте, значит мы нашли искомое разбиение, и наша перестановка была чётной.

2. Последние два элемента не на месте, то есть они поменяны местами. Значит текущая перестановка отличается от нашей одной транспозицией, но текущая перестановка чётная, значит наша нечётная.

Ниже приведена реализация

bool parity(const vector<int> &p) {
    int n = p.size();
    if (n == 1) return false;
    vector<int> cur(n);
    vector<int> inv_cur(n);
    iota(cur.begin(), cur.end(), 0);
    iota(inv_cur.begin(), inv_cur.end(), 0);
    auto do_cycle = [&](int i, int j, int k) {
        int tmp = cur[k];
        cur[k] = cur[j];
        cur[j] = cur[i];
        cur[i] = tmp;

        inv_cur[cur[i]] = i;
        inv_cur[cur[j]] = j;
        inv_cur[cur[k]] = k;
    };
    for (int i = 0; i < n - 2; i++) {
        if (cur[i] != p[i]) {
            int j = inv_cur[p[i]];
            if (j != n - 1) {
                do_cycle(n - 1, j, i);
            } else {
                do_cycle(n - 2, j, i);
            }
        }
    }
    return cur[n - 1] != p[n - 1];
}

Тем самым мы доказали теорему, и нашли простой алгоритм, позволяющий за $$$O(n)$$$ вычислить четность перестановки.