103773: [Atcoder]ABC377 D - Many Segments 2

Problem Statement

You are given two sequences of positive integers of length $N$, $L=(L_1,L_2,\ldots,L_N)$ and $R=(R_1,R_2,\ldots,R_N)$, and an integer $M$.

Find the number of pairs of integers $(l,r)$ that satisfy both of the following conditions:

• $1\le l \le r \le M$
• For every $1\le i\le N$, the interval $[l,r]$ does not completely contain the interval $[L_i,R_i]$.

Constraints

• $1\le N,M\le 2\times 10^5$
• $1\le L_i\le R_i\le M$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

Output

Print the answer.

Sample Input 1

2 4
1 2
3 4

Sample Output 1

5

The five pairs $(l,r)=(1,1),(2,2),(2,3),(3,3),(4,4)$ satisfy the conditions.

For example, $(l,r)=(1,3)$ does not satisfy the conditions because the interval $[1,3]$ completely contains the interval $[1,2]$.

Sample Input 2

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

Sample Output 2

0

There may be cases where no pairs of integers satisfy the conditions.

Sample Input 3

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

Sample Output 3

102

问题陈述

给定两个长度为$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$

输出

打印答案。

样本输入 1

2 4
1 2
3 4

样本输出 1

5

满足条件的五个整数对$(l,r)=(1,1),(2,2),(2,3),(3,3),(4,4)$。

例如，$(l,r)=(1,3)$不满足条件，因为区间$[1,3]$完全包含了区间$[1,2]$。

样本输入 2

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

样本输出 2

0

可能存在没有整数对满足条件的情况。

样本输入 3

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

样本输出 3

102