G - Another Shuffle Window
对于一个长度为 k 的两两不同的序列，其期望逆序对数为 \dfrac{k\times (k-1)}{4}。
因为序列中一共有 \dfrac{k\times (k-1)}{2} 对数，每一对为逆序对的概率为 \dfrac{1}{2}，所以其期望逆序对数为 \dfrac{k\times (k-1)}{4}。
设原序列的逆序对数为 C，[i,i+k-1] 这个区间的逆序对数为 x。
将 [i,i+k-1] 随机打乱之后，由于只改变了 [i,i+k-1] 这个区间内部的逆序对，整个序列期望的逆序对数变为 C-x+\dfrac{k\times (k-1)}{4}。
那么只需要求出 x 就做完了。
设 [i,i+k-1] 的逆序对数为 x，那么将区间改变为 [i+1,i+k] 时逆序对数怎么变化呢？
区间平移过后，减少了 p_i 对答案的贡献，具体就是答案减少了 [i + 1，i+k-1] 中比 p_i 小的数的个数。
增加了 p_{i+k} 对答案的贡献，具体就是答案增加了 [i+1,i+k-1] 中比 p_{i+k} 大的数的个数。
上述操作用 Fenwick Tree 维护即可。
由于有 n-k+1 个区间，将每个区间的答案累加后，还要乘上 \dfrac{1}{n-k+1}。
总时间复杂度 \mathcal O(n\log n)。
参考代码