4372. 区间

【题目背景】

区间套区间套区间。

【题目描述】

给你 $n$ 个区间 $[l_i,r_i]$。

定义 $f(L,R)$ 表示下标在 $[L,R]$ 的所有区间在一条数轴上覆盖的单位长度。

多次询问，给定区间 $[A,B]$，求从区间 $[A,B]$ 中任意选择一个子区间 $[L,R]$，求 $f(L,R)$ 的期望值。

答案对 $666623333$ 取模。

【输入格式】

第一行两个数 $n,m$，分别是区间个数和询问个数。

接下来 $n$ 行，每行两个整数 $l_i,r_i$。表示一个区间。

接下来 $m$ 行，每行两个整数 $A,B$，表示一份询问。

【输出格式】

$m$ 行，每行一个正整数表示答案。

【样例输入1】

2 1
1 5
4 8
1 2

【样例输出1】

5

【样例输入2】

5 5
12 45
67 89
23 56
34 78
10 100
1 3
2 4
1 5
3 5
2 2

【样例输出2】

44
555519490
355532508
67
22

【样例说明】

当 $L=1,R=1$ 时，$f(1,1)=5-1=4$。

当 $L=2,R=2$ 时，$f(2,2)=8-4=4$。

当 $L=1,R=2$ 时，$f(1,2)=8-1=7$。

所以期望值为 $\frac{4+4+7}{3}=5$。

【数据规模与约定】

对于 $20\%$ 的数据，满足 $n,m\le 500$。

对于 $40\%$ 的数据，满足 $n,m\le 5000$。

对于 $60\%$ 的数据，满足 $n,m\le 50000$。

对于 $100\%$ 的数据，满足 $n,m\le 500000$，$0<l_i<r_i<666623333$。$1\le A\le B\le n$。

【来源】

常3.14

大洋里。