当前没有测试数据。

D - Many Segments 2

多条线段 2

分值：400 分

题目描述

给定长度为 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]$。

约束条件

• $1\le N,M\le 2\times 10^5$
• $1\le L_i\le R_i\le M$
• 所有输入的值均为整数。

输入格式

从标准输入按如下格式读入数据：

$N$ $M$

$L_1$ $R_1$

$L_2$ $R_2$

$\vdots$

$L_N$ $R_N$

输出格式

输出答案。

样例输入输出

2 4
1 2
3 4

5

这 5 组数对 \((l,r)\)=(1,1),(2,2),(2,3),(3,3),(4,4) 满足条件。 例如，\((l,r)\)=(1,3) 不满足条件，因为区间 \([1,3]\) 完全包含区间 \([1,2]\)。

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

原题链接