9493.性质不同的数字

Time Limit: 4s Memory Limit: 512MB

在一个无限长的数轴上,有 $n$ 个集合,每个集合给定一个范围 $[l, r]$,其中 $l$ 和 $r$ 为整数,且满足 $l \leq r$。我们称两个整数 $x$ 和 $y$ 性质不同,当且仅当存在 至少一个集合 $S$,使得 $x$ 属于 $S$ 但 $y$ 不属于 $S$,或者 $x$ 不属于 $S$ 但 $y$ 属于 $S$。

你的任务是计算在这个数轴上最多可以选出多少个数,使得这些数的性质两两不同。

Input Format(From the terminal/stdin)

第一行包含一个整数 $t$,表示测试样例的组数($1 \leq t \leq 10000$)。

每组测试样例的格式如下:

  • 第一行包含一个整数 $n$,表示集合的数量($0 \leq n \leq 200000$)。
  • 接下来的 $n$ 行,每行包含两个整数 $l$ 和 $r$,表示集合的范围($0 \leq l \leq r \leq 10^9$)。

保证所有测试样例的 $n$ 的总和不超过 $10^6$。

Output Format(To the terminal/stdout)

对于每组测试样例,输出一个整数,表示数轴上最多可以选出的性质两两不同的数的数量。

Sample Input

Copy
3
1
1 6
4
0 12
4 13
6 13
12 13
0 \n
 \n
 · \n
 \n
 ·  \n
 ·  \n
 ·  \n
  ·  \n
 \n

Sample Output

Copy
2
6
1 \n
 \n
 \n
Source: 2025“钉耙编程”中国大学生算法设计暑期联赛(3), HDU, 8009

Submit

请先 登录

© 2025 FAQs