CF1956F Nene and the Passing Game

Nene 正在作为篮球教练训练她的队伍。Nene 的队伍由 $n$ 名球员组成，编号从 $1$ 到 $n$。第 $i$ 名球员有一个臂展区间 $[l_i, r_i]$。只有当 $|i-j| \in [l_i+l_j, r_i+r_j]$（其中 $|x|$ 表示 $x$ 的绝对值）时，两名球员 $i$ 和 $j$（$i \neq j$）才能互相传球。 Nene 想要测试这些球员的配合能力。为此，她将举行若干轮考核。 - 在每一轮中，Nene 会选择一个球员序列 $p_1, p_2, \ldots, p_m$，使得对于所有 $1 \leq i < m$，球员 $p_i$ 和 $p_{i+1}$ 能够互相传球。序列的长度 $m$ 可以由 Nene 自由选择。每名球员可以在序列 $p_1, p_2, \ldots, p_m$ 中出现多次，也可以一次都不出现。 - 然后，Nene 会将球传给球员 $p_1$，球员 $p_1$ 再传给球员 $p_2$，以此类推……球员 $p_m$ 会把球扔出篮球场，球就不能再使用了。 作为教练，Nene 希望每一名球员都至少在一轮考核中出现。由于 Nene 放学后还要约会，她希望你计算完成任务所需的最少考核轮数。

每个测试用例包含多组数据。第一行包含测试用例的组数 $t$（$1 \leq t \leq 2 \cdot 10^5$）。接下来是每组测试用例的描述。 每组测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^6$），表示球员人数。 接下来的 $n$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$），表示第 $i$ 名球员的臂展区间。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^6$。

对于每组测试用例，输出一个整数，表示 Nene 完成任务所需的最少考核轮数。

在前两个测试用例中，Nene 可以举办两轮考核：一轮为 $p=[1]$，另一轮为 $p=[2]$。可以证明只举办一轮考核是不够的，因此答案是 $2$。 在第三个测试用例中，Nene 可以举办两轮考核：一轮为 $p=[1,3]$，另一轮为 $p=[2]$。球员 $1$ 可以将球传给球员 $3$，因为 $|3-1|=2 \in [1+1,3+3]$。可以证明只举办一轮考核是不够的，因此答案是 $2$。 由 ChatGPT 4.1 翻译