【专题】排列逆序数的奇偶性

排列逆序数的奇偶性是一个十分常见的属性。不同于直接求逆序数，由于排列的性质，这玩意是可以 \(\mathcal O(n)\) 直接求解的。为了完成这一点，引入如下基本结论：

1. 排列两元素对换，逆序数奇偶性改变。
2. 排列的逆序数同余 \(n - \#\)环。

第一点，在大多数线性代数教材中都有所提及。

第二点中的 “环” 的构造方式：按下标 \(i\) 向 \(p_i\) 连边，或者说，两排列之间连边，必形成若干环（这是因为每个数都出现一次，对应的度数也为 \(1\)）。

为啥是这个数？证明详见 CodeForces Blog: https://codeforces.com/blog/entry/97849?#comment-866870

这个结论十分有用。

• CF1591D
• CF911D
• CF987E
• ABC296F

有点记不清了但至少 ABC 出过三四次了，每次看蒋老师代码都觉得“哦，这tm我学过啊”真是十分常见的结论。下附代码：

bool parity = n & 1;
for (int i : p) if (~i) {
    for (int j = i; ~j; ) {
        std::tie(j, p[j]) = std::tuple{p[j], -1};
    }
    parity ^= 1;
}