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 种情况。