本题考察了 DP，组合数学的相关知识。

30pts

我们用计数 $dp$。

设 $dp_{i,j}$ 表示前 $i$ 个数，最后一个数是 $j$ 的合法方案数，转移：$dp_{i,j} = \sum_{k \geq j} dp_{i-1,k}$。

+30pts

考虑 $l_i=l_j$，$r_i=r_j$，假设 $A=r_i-l_i+1$，问题相当于求解值域 $[1,A]$ 的不增序列，可以直接利用组合数插板法分析出答案。

80pts

上面两档分启发我们同时从 DP 和组合的角度考虑问题。

用每个 $L_i, R_i$ 做分界点，把所有的数分组。

设离散化的数组为 $re$，则第 $i$ 组的数包括 $[re_i, re_{i+1})$。

这样我们可以愉快地 $dp$ 了，设 $dp_{i,j}$ 表示前 $i$ 个数，最后一个数在第 $j$ 组的合法方案数。通过枚举 $k$，表示 $a_{k+1,···,i}$ 全在第 $j$ 组，进行转移：

$$dp_{i,j} = \sum_{k=1}^{i-1} \sum_{p>j} dp_{k,p} \times \binom{len + i - k - 1}{len - 1}$$

100pts

这个内层求和显然可以用前缀和优化，所以总时间复杂度为 $O(n^3)$。