逆序对与期望

母题—逆序对与期望

求长度为 $n$ 的排列的期望的逆序对个数。

对于每一对数，是否成为逆序对的概率显然为 $\frac{1}{2}$，那么就有：

$E(x) = E(\sum\limits_{i,j\mid i < j}[a_i > a_j])=\sum\limits_{i,j\mid i < j}(E([a_i > a_j]) = \sum\limits_{i,j\mid i < j} \frac{1}{2} = \frac{n(n-1)}{4}$

变式 $1$ Another Shuffle Window

题意： 每次可以选择一个长度为 $k$ 的连续区间进行重排，求期望的逆序对个数。

每次选择一对 $(a_i,a_j)$ 去考虑是否可以产生贡献。对于一个长度固定的区间，可以分区间内和区间内外分别考虑。对于后者，无论区间内怎么重排，都可以直接计算出与区间外的逆序对数，像滑动窗口一样直接处理即可。

变式 $2$ Inversions After Shuffle

每次可以选择任意长度的连续区间进行重排，求期望的逆序对个数。

根据选择的 $(a_i,a_j)$ 是否会产生贡献从而列出式子，并用数据结构维护。显然所有的区间数为 $C_n^1 + C_n^2 = C_{n + 1}^2 = \frac{n(n + 1)}{2}$，则对于这一对数（显然此时 $i \neq j$），令 $i < j$，有 $\frac{2i(n - j + 1)}{n(n + 1)}$ 的概率被一个区间包含。而 $(a_i,a_j)$ 又有 $\frac{1}{2}$ 的概率成为逆序对。

若 $a_i,a_j$ 被选中，则贡献的答案为

$\sum \limits_{i = 1} ^ n \sum \limits_{j = i + 1}^n \frac{1}{2}\frac{2i(n - j + 1)}{n(n + 1)}\\ =(1 \frac{n(n - 1)}{2} + 2 \frac{(n - 1)(n - 2)}{2} + \cdots + n\frac{1 \times 0}{2}) \times \frac{1}{n(n + 1)}\\ = \frac{1}{2n(n + 1)} \sum \limits_{i = 1}^n i(n - i + 1)(n - i)$

若不被选中，则只有当 $a_i > a_j$ 时才会产生贡献，答案为

$\sum \limits_{i = 1}^n \sum \limits_{j = i + 1}^n [1 - \frac{2i(n - j + 1)}{n(n + 1)}] [a_i > a_j]\\ =\sum \limits_{i = 1}^n \sum \limits_{j = i + 1}^n [a_i > a_j] - \frac{2}{n(n + 1)}\sum \limits_{i = 1}^n (i\sum \limits_{j = i + 1}^{n}(n - j + 1)[a_i > a_j])$

对于前者，直接循环维护即可。对于后者，用树状数组维护逆序对。但需要注意循环枚举应该从后往前，从而保证每次查询时在其之后的数的相对大小已存入树状数组中。

for (int i = n;i;--i)
{
    sum += 1.0 * i * query (a[i]);
    modify (a[i],n - i + 1);
}

变式 $3$ Inversion Expectation

题意：长度为 $n$ 的排列中有一些数是不确定的，求该排列的逆序对。

分类讨论，共三种情况：

两个已知数构成逆序对树状数组求解即可。
两个未知数构成逆序对用母题的结论 $\frac{n(n - 1)}{4}$ 即可。
一个未知数，一个已知数设已知数 $a$ 前面的未知数个数为 $k$，比 $a$ 大的未知数个数为 $m$，总共的未知数个数为 $n$，则此时的贡献为 $k \times \frac{m}{n}$。那么在后面的比 $a$ 小的未知数的贡献同理。

Shohag Loves Inversions

题意： 初始时 $a = [0,1]$，每次更新将 $a$ 逆序对的数量 $k$ 插入其中，求最终长度为 $n$ 的序列的数量。

以下均设当前的序列逆序对的数量为 $k$。

首先需要通过观察得出一个性质，当序列第一次出现 $k > 1$ 的时候，若将 $k$ 插在中间的位置，会使得 $k’ > k$，在末尾插入则 $k’ = k$。设 $f_i$ 表示长度为 $i$ 且当前第一次出现 $k > 1$ 时，变为长度为 $n$ 的序列的数量。剩下还有 $n - i$ 次操作，可以将 $k$ 均插入末尾，或者在末尾插入若干个以后再将 $k$ 插入中间的 $i$ 个位置之一，因此可以得到以下转移：

$f_i = i \times \sum \limits_{j = 0}^{n - i - 1} f_{i + j + 1} + 1$

现在我们讨论整一个序列均为 $k \le 1$ 的情况。显然 $k = 0$ 时就只有 $\underbrace{00 \cdots 0}_{n - 1}1$ 这一种。而 $k = 1$ 时应为 $\underbrace{00 \cdots 0}_{x}010\underbrace{11\cdots1}_{n - x - 3}$，其中 $x \in [0,n - 3]$，故有 $n - 2$ 种。所以说，$k \le 1$ 时，共有 $n - 1$ 种。

最后考虑 $k \le 1$ 转移至 $k > 1$ 的情况，显然只有 $k = 1$ 时才有可能。因此对于 $\underbrace{00 \cdots 0}_{x}010\underbrace{11\cdots1}_{n - x - 3}$ 类型的串，我们需要找到第一个 $1$ 所出现的位置。不难发现第一次出现 $k > 1$ 的序列时至少由长度为 $3$ 的 $010$ 转移而来，共会产生 $2$ 个长度为 $4$ 且 $k > 1$ 的串 $1010,0110$。一般化的，若在长度为 $i$ 时第一次出现 $k > 1$，则这个长度为 $i$ 的串共会有 $\sum \limits_{j = 2}^{i - 1} = \frac{i(i - 3)}{2}$ 种情况。举个例子，若 $i = 5$，则可能由 $0010,0101$ 转移出 $5$ 种情况。

综上所述，最后的答案就是 $n - 1 + \sum \limits _{i = 4}^n \frac{i(i - 3)}{2} f_i$。直接后缀和进行处理即可，时间复杂度 $O(n)$。