随机数列逆序对数

期望线性性：对于两个数 \(x,y(x<y)\)，他们产生逆序对的概率是 \(\dfrac y{y+x}\)（考虑 \(x,y\) 最后一个同时出现的时刻，如果选中 \(y\) 出来那么有逆序对，否则没有）

所以变成求 \(\displaystyle{\sum_{i=1}^n\sum_{j=1}^{i-1}cnt_icnt_j \frac i{i+j}}\)

这是一个差卷积的模型，但是由于限制了 \(j<i\) 那么需要半在线卷积。zero4338 说也可以用他博客里面的技巧优化