← 返回题目列表

Codeforces · 1956/F

F. 内内和传球游戏

中文机器翻译题面 查看原题

Nene 正在作为篮球教练训练她的球队。 Nene 的团队由 $$$n$$$ 玩家组成,编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 个玩家的手臂间隔为 $$$[l_i,r_i]$$$。两个球员 $$$i$$$ 和 $$$j$$$ ($$$i \neq j$$$) 可以互相传球当且仅当 $$$|i-j|\in[l_i+l_j,r_i+r_j]$$$ (这里,$$$|x|$$$ 表示 $$$x$$$ 的绝对值)。

内内想要测试这些玩家的合作能力。为了做到这一点,她将进行多轮考核。

- 在每一轮中,Nene 将选择一系列玩家 $$$p_1,p_2,\ldots,p_m$$$,使得玩家 $$$p_i$$$ 和 $$$p_{i+1}$$$ 可以在所有 $$$1 \le i < m$$$ 情况下将球传给对方。序列 $$$m$$$ 的长度可以由 Nene 选择。每个玩家可以在 $$$p_1,p_2,\ldots,p_m$$$ 序列中出现多次,也可以根本不出现。
- 然后,Nene 会将球扔给玩家 $$$p_1$$$,玩家 $$$p_1$$$ 会将球传给玩家 $$$p_2$$$ 等等...玩家 $$$p_m$$$ 会将球扔出篮球场,使其无法再使用。

作为一名教练,Nene 希望每位 $$$n$$$ 球员至少出现在一轮评估中。由于内内必须放学后去约会,内内希望你计算完成任务所需的最少评估轮数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 2\cdot 10^5$$$)。测试用例的描述如下。

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 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 完成工作所需的最少评估轮数。

示例

输入 #1

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

输出 #1

2
2
2
1
3

注意

在前两个测试用例中,Nene 可以主持两轮评估:一轮评估为 $$$p=[1]$$$,另一轮评估为 $$$p=[2]$$$。可以看出,举办一轮评估是不够的,所以答案是$$$2$$$。

在第三个测试用例中,Nene 可以主持两轮评估:一轮评估为 $$$p=[1,3]$$$,另一轮评估为 $$$p=[2]$$$。玩家 $$$1$$$ 可以将球传给玩家 $$$3$$$,如 $$$|3-1|=2 \in [1+1,3+3]$$$。可以看出,举办一轮评估是不够的,所以答案是$$$2$$$。