CF749E Inversions After Shuffle

题意 ： 给出一个长度为 的排列 ，等概率随机选取一个区间 ，将其随机打乱，问逆序对个数的期望。

，时限 。

---

考虑每个无序二元组 之间的贡献。

若随机区间 包含 ，概率为

（注： 是选择一个区间的方案数）

产生逆序对的概率为 。

这部分的贡献总和为：

若随机区间 不完全包含 两者，概率为

此时， 的相对顺序不会改变，于是贡献为

这部分的贡献总和为：

容易使用树状数组求出。复杂度为 。