题目大意

有一个数列 $A$ ，数列上的每个数都是在 $[l_i,r_i]$ 范围内随机的数。
将这个数列进行稳定排序，得到每个位置在排序后的排名 $p_i$ 。
$f(A)=sum s_ip_i$ ，求 $E(f(A))$ 。

思考历程

这种恶心的概率题根本就不知道该怎么思考好吗！
于是打了个暴力，就是枚举所有的情况，然后直接计算。
可是最后不知道为什么爆0了……

正解

$E(f(A))=sum s_i E(p_i)$
所以我们只需要求出 $p_i$ 的期望值就好了。
显然 $p_i=sum_{jleq i} |a_j leq a_i|+sum_{j>i} |a_j< a_i|$
左右两边是类似的，下面只考虑左边的情况。
设 $a_i=x$ 。对于每个位置 $j$ ，有三种情况：
1、当 $x<l_j$ 时，位置 $j$ 作出的贡献为 $0$ 。
2、当 $l_j leq x leq r_j$ 时，位置 $j$ 做出的贡献为 $frac{x-l_i+1}{r_i-l_i+1}$ 。
3、当 $x>r_j$ 时，位置 $j$ 作出的贡献为 $1$ 。
不解释……
可以将其转化成一个分段函数的图像来理解一下，前后两段都是与 $x$ 轴平行的线，中间的那段是一段一次函数的图像。
将所有 $j$ 的函数全部加起来，枚举 $x$ ，就可以计算 $E(p_i)$ 。
接下来我们考虑的问题是如何将所有 $j$ 的函数叠加起来，并且能够快速查询一段区间内的和。
在叠加之后，函数长得一定很奇怪……所以不能用数学方法。
考虑使用线段树，用线段树来维护这些东西。
现在有一个奇怪的操作，在线段树内的一段区间上加某段一次函数的图像。
换个说法就是给这段区间加上一个等差数列。
这个怎么维护呢？
我们发现最重要的一点就是标记，关键是如何维护标记。
合并标记的时候，两段一次函数的都在同一段区间内，仔细想想是可以合并的。
一次函数的普遍形式就是 $y=kx+b$ ，合并起来之后就是 $y=(k_1+k_2)x+(b_1+b_2)$ 。所以可以简单粗暴地相加。
这样维护标记的问题就解决了，整个区间的值都可以维护。
下一个问题就是如何快速地询问，直接维护和就好，在修改的时候加上等差数列的和（千万不要告诉我你不会等差数列求和）。
算法的核心就完成了。
所以我们维护一个这样的线段树，然后从左往右扫，将当前点的贡献（也就是那个分段函数）加入线段树当中，然后区间询问当前点取值范围这一区间内的和，计算 $E(p_i)$ 。
再从右往左扫，实际上是类似的。

代码

~~我才不会告诉你我先打了博客再打代码……~~