CF1834D Survey in Class

Zinaida Viktorovna 有 $n$ 名历史课学生。今天的作业包含 $m$ 个主题，但学生们准备时间很少，第 $i$ 个学生只学习了从 $l_i$ 到 $r_i$（包含两端）的主题。 上课开始时，每个学生的手的位置都是 $0$。老师想要提问一些主题，过程如下： - 老师提问第 $k$ 个主题。 - 如果某学生学过第 $k$ 个主题，他的手上升 $1$，否则下降 $1$。 每个主题 Zinaida Viktorovna 最多只能提问一次。 请你求出，在提问结束后，班级中最高的手和最低的手之间的最大高度差。 注意，学生的手可以低于 $0$。

每个测试点包含多组测试数据。第一行包含测试组数 $t$（$1 \le t \le 10^4$）。接下来是每组测试数据的描述。 每组测试数据的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 10^5, 1 \le m \le 10^9$），分别表示学生人数和主题数。 接下来 $n$ 行，每行两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le m$），表示第 $i$ 个学生学习的主题区间。 保证所有测试数据中 $n$ 的总和不超过 $10^5$。

对于每组测试数据，输出一个整数，表示提问结束后班级中最高的手和最低的手之间的最大高度差。

在第一个测试点中，Zinaida Viktorovna 可以提问主题 $5, 6, 7, 8$。这样第 $2$ 个学生的手高度为 $4$，第 $4$ 个学生的手高度为 $-2$，因此差值为 $6$。 在第二个测试点中，可以提问主题 $1$ 和 $3$。这样第 $1$ 个学生的手高度为 $2$，第 $3$ 个学生的手高度为 $-2$，因此差值为 $4$。 在第三个测试点中，无论提问哪些主题，最高和最低的手的高度差都为 $0$。 在第五个测试点中，可以提问所有主题。这样第 $1$ 个和第 $3$ 个学生的手的高度差为 $12$。 由 ChatGPT 4.1 翻译