AIO 2025 第 2 题：埋藏的宝藏

英文题名：Buried Treasure

题目描述

世世代代以来，比特海滩（Bitwise Beach）的岸边一直流传着一个故事：有一份宝藏埋藏在海滩之下。

你知道，宝藏藏在 (L) 个互不相同的位置之一，这些位置依次编号为 (1) 到 (L)。

在与比特海滩的当地人交谈后，你得到了 (N) 条线索。第 (i) 条线索由两个整数 (A_i) 和 $(B_i)$组成，其中 (A_i\le B_i)。这条线索表示宝藏位于 (A_i) 到 (B_i) 之间的某个位置，包含两个端点。

例如，若 (A_i=3) 且 (B_i=6)，则宝藏一定在位置 (3)、(4)、(5) 或 (6)。

为了节省时间，并抢在其他寻宝者之前找到宝藏，你希望挖掘的位置尽可能少。因此，你想知道：

有多少个位置与全部 (N) 条线索都相符？

答案可能为 (0)，这意味着当地人欺骗了你！

子任务与数据范围

你的程序将使用多组未公开测试数据进行评测。所有测试数据均满足：

• (2\le N\le 200,000)
• (1\le L\le 1,000,000)
• 对所有 (i)，均有 (1\le A_i\le B_i\le L)

测试数据被划分为若干子任务。只有正确通过某个子任务中的全部测试数据，才能获得该子任务的分数。

输入格式

你的程序必须读取输入并输出结果。建议使用竞赛网站提供的程序模板来帮助处理输入与输出。

• 第一行包含两个整数 (N) 和 (L)。
• 接下来 (N) 行描述各条线索，其中第 (i) 行包含两个整数 (A_i) 和 (B_i)。

输出格式

输出一个整数，表示与全部 (N) 条线索都相符的位置数量。

样例 1

样例输入 1

2 10
3 6
5 8

样例输出 1

2

样例 2

样例输入 2

2 6
1 6
2 5

样例输出 2

4

样例 3

样例输入 3

2 8
7 8
1 3

样例输出 3

0

样例 4

样例输入 4

5 20
3 13
7 15
6 14
2 12
1 20

样例输出 4

6

样例解释

• 在样例 1 中，共有 (N=2) 条线索，比特海滩共有 (L=10) 个位置。第一条线索说明宝藏位于位置 (3)、(4)、(5) 或 (6)；第二条线索说明宝藏位于位置 (5)、(6)、(7) 或 (8)。只有位置 (5) 和 (6) 同时符合两条线索，因此答案为 (2)。

• 在样例 2 中，共有 (N=2) 条线索，比特海滩共有 (L=6) 个位置。第一条线索说明宝藏位于位置 (1)、(2)、(3)、(4)、(5) 或 (6)；第二条线索说明宝藏位于位置 (2)、(3)、(4) 或 (5)。只有位置 (2)、(3)、(4) 和 (5) 同时符合两条线索，因此答案为 (4)。

• 在样例 3 中，共有 (N=2) 条线索，比特海滩共有 (L=8) 个位置。第一条线索说明宝藏位于位置 (7) 或 (8)；第二条线索说明宝藏位于位置 (1)、(2) 或 (3)。没有任何位置同时符合两条线索，因此答案为 (0)。

• 在样例 4 中，共有 (N=5) 条线索，比特海滩共有 (L=20) 个位置。共有 (6) 个位置符合全部线索，分别是 (7)、(8)、(9)、(10)、(11) 和 (12)。

说明：原题没有图示或脚注。