题解：AT_abc380_g [ABC380G] Another Shuffle Window

不会算期望，但是可以算所有方案的逆序对总数最后除以方案数。

方案数是 n - k + 1 个区间每个区间有 k! 种方案共 (n - k + 1)\cdot k!。

一个长度为 i 的排列的全排列所有逆序对数的递推式是 f_i = if_{i - 1} + \frac{i(i - 1)}{2}(i - 1)!。
怎么得到的：
考虑已知 f_{i - 1}，求 f_i 时依次让 1\sim i 作为第一位，第一位和后面的贡献分别为 0\sim i - 1，且每个数作第一位有 (i - 1)! 种方案，后 i - 1 位的逆序对数即为 f_{i - 1}，贡献了 i 次。

算一个区间的所有方案的逆序对总数时当前区间内的逆序对单独考虑，剩下的逆序对不变重复贡献 k! 次。
维护区间逆序对由于只有从前面删数和从后面插入数所以直接树状数组维护当前区间有那些数即可。
删数时会减去后面区间里小于它的数，加数会加上前面区间里大于它的数。

Code