AT_abc377_d [ABC377D] Many Segments 2
题目描述
给定长度为 $N$ 的正整数列 $L=(L_1,L_2,\ldots,L_N),R=(R_1,R_2,\ldots,R_N)$ 和整数 $M$。
求同时满足以下条件的整数组 $(l,r)$ 的个数。
- $1\le l\le r\le M$
- 对于所有 $1\le i\le N$，区间 $[l,r]$ 不完全包含区间 $\left[L_i,R_i\right]$。
输入格式
输入按照如下标准给出：
> $N$ $M$\
> $L_1$ $R_1$\
> $L_2$ $R_2$\
> $\vdots$\
> $L_N$ $R_N$
输出格式
输出答案即可。
说明/提示
#### 约定
- $1\le N,M\le 2\times 10^5$
- $1\le L_i\le R_i\le M$
- 所有输入均为整数
$(l,r)=(1,1),(2,2),(2,3),(3,3),(4,4)$ 这 $5$ 个都满足条件。
例如 $(l,r)=(1,3)$ 不满足条件。这是因为区间 $[1,3]$ 完全包含了区间 $[1,2]$。
此时不存在满足条件的整数对。
Translation by @[$\frak{Lorentz}$](/user/1232305) and @[Jie_XuSheng](/user/1332013)。