$n\le 10$

暴搜，时间复杂度 $O(n!m)$，期望得分 $20$。

$n\le 300$

令 $p_u$ 表示 $u$ 的父亲节点。根据 $l_i\le r_i<i$，不难有 $p_u<u$。

设 $u<v$，则 $p_v$ 一定在 $(u,v)$ 的路径上。

考虑证明：若 $p_v$ 不在 $(u,v)$ 路径上，当且仅当 $v$ 时 $u$ 的祖先，根据 $p_u<u$ 可以得到 $u$ 的祖先编号小于 $u$，即 $u>v$，与 $u<v$ 矛盾，故原命题得证。

以上完成本题最为关键的结论证明。

若对于每一次加操作，都暴力完成，复杂度显然是指数级。

不过对于每一种加操作，都可以用 $(u,v)$ 表示（下文均假设 $u<v$）且 $(u,v)$ 的加操作可以转化为 $(u,p_v)$ 的加操作。

若对链 $(a,b)$ 的加操作对链 $(c,d)$ 的加操作有转化，必须满足 $b<d$。且对于 $a\ne b$ 的情况，对链 $(a,c)$ 的加操作和链 $(b,c)$ 的加操作之间不会互相转化。

也就是说，我们以第二维按照 $v$ 划分所有链，可以分成若干层，当前层只会影响这层之前的层，且层内部之间不会影响。

可以设计出一个递推状物，设 $g_{u,v}$ 表示所有操作对 $(u,v)$ 这条链加上的期望值，则有：

$${g_{u,p_v}\gets g_{u,p_v}+\frac{g_{u,v}}{r_v-l_v+1}},  u<p_u  $$

$${g_{p_{v},u} \gets g_{u,p_v}+\frac{g_{u,v}}{r_v-l_v+1}},  u>p_u$$

注意到编码过程中，为了方便讨论，我们始终只对 $u<v$ 的状态操作，因此若出现 $p_v<u$ 的情况，要操作 $g_{p_v,u}$ 而不是 $g_{u,p_v}$。

其实是简单排列组合原理，每一层内部的转移因为无所谓，所以第一维的枚举顺序可以随便来。

递推完所有的 $g_{u,v}$ 后，考虑计算点 $u$ 的答案，根据结论，只要 $v<u$，那么 $(v,u)$ 的路径一定包含 $(p_u,u)$ 这条链，且对于任意 $(a,u),(b,u)$ 之间互不影响，说明 $(a,u),(b,u)$ 代表的加操作独立，可以直接加起来。

因此答案为 $\sum_{v<u}g_{v,u}$。直接做需要枚举每个点的父亲，时间复杂度 $O(n^3+m)$。期望得分 $60$。

$n\le 2000$

考虑优化这个过程，把 $g$ 数组当成一个二维平面，代码中 $k>i$ 的部分实际上是对横着的一段加上了一个数。$k<i$ 的部分是对竖着的一段加上了一个数。

可以用二维差分优化，递推的过程中求差分的前缀和数组，因为要求前缀和，所以第一维的枚举顺序也需要确定。

时间复杂度 $O(n^2+m)$，期望得分 $100$。