还是 min-max 容斥加 DP。
相当于求 $\displaystyle E(\max_{i=1}^q \min_{j=l_i}^{r_i} a_j)$，其中 $a_j$ 是值域为 $[1,m]$ 随机数列。最小值的最大值并不好处理，利用 min-max 容斥转化为最小值的最小值，得到 ：$\displaystyle \sum_{T\subseteq S} (-1)^{|T|+1} E(\min_{i\in T} \min_{j=l_i}^{r_i} a_j)$。注意到后面的部分只和区间集合的区间并的大小有关，这个也可以通过 DP简单求出。主要考虑求容斥系数。将并集大小压进状态，设计状态 $f(i,j)$ 表示选取到位置 $i$，并集长度为 $j$ 的容斥系数。