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

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

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

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

这个结论十分有用。

~~有点记不清了但至少 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;
}