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]$ 不完全包含区间 $[L_i,R_i]$。

输入格式

输入由标准输入按以下格式给出：
$N$ $M$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

输出格式

输出答案。

2 4
1 2
3 4

5

6 5
1 1
2 2
3 3
4 4
5 5
1 5

0

6 20
8 12
14 20
11 13
5 19
4 11
1 6

102

提示

$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)$ 满足条件。
例如，$(l,r)=(1,3)$ 不满足条件，因为区间 $[1,3]$ 完全包含区间 $[1,2]$。
也可能存在没有任何整数对满足条件的情况。

标签: AtCoder|abc377D

来源

AtCoder|abc377D