AT_ajo2024_final_d Shooting the Stars

在数轴上有 $N$ 个星星，按照坐标从小到大的顺序编号为 $1$ 到 $N$。第 $i$ 个星星（$1 \leq i \leq N$）的坐标是 $X_i$，亮度是 $A_i$。 AtCoder 想要拍摄其中一些星星的照片。AtCoder 可以自由选择数轴上的一个区间，把该区间内的星星拍摄下来。在照片中，某些星星可能因为太亮而被看作同一个星星。具体规则如下： 1. 若星星 $i$ 和星星 $j$ 满足 $|X_i - X_j| \leq A_i + A_j$，这两颗星会被视为同一颗星。 2. 如果星星 $i$ 和 $k$ 被视为同一颗星，星星 $k$ 和 $j$ 也被视为同一颗星，那么星星 $i$ 和 $j$ 也会被视为同一颗星（具有传递性）。 3. 按上面规则没有判为同一颗星的星星，会被视为不同的星星出现在照片上。 需要注意：没有被选入拍摄区间的星星，不会出现在照片上，也不会参与“同一颗星”的合并判断。 请问，合理选择一个区间，照片上能够出现的最多不同星星的数量是多少？ 给定 $T$ 组测试数据，请分别输出答案。

输入以如下格式由标准输入给出。这里 $\mathrm{case}_i$ 表示第 $i$ 个测试数据。 > $T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$ 每个测试数据的格式如下： > $N$ $X_1$ $A_1$ $X_2$ $A_2$ $\vdots$ $X_N$ $A_N$

请输出每组测试数据的答案。

### 样例解释 1 下面举出第 $1$ 个测试数据的两种拍摄方式。 1. 选择坐标 $0$ 到 $5$ 的区间：星星 $1, 2$ 会出现在照片上。$|X_1 - X_2| = 3, A_1 + A_2 = 2$，所以星星 $1, 2$ 会被分为不同的星星。 2. 选择坐标 $0$ 到 $9$ 的区间：星星 $1, 2, 3, 4$ 会出现在照片上。因为第一个规则，星星 $1, 3$，$2, 3$，$3, 4$ 合并。由于规则的传递性，$1, 2, 3, 4$ 都被归为同一颗星。 在此测试用例中，最多能拍到 $2$ 颗不同的星星，其中一种方式是方法 1。如果按方法 2，全被当成 1 颗星，结果不是最优的。 第 $2$ 个测试用例，最多能拍到 $3$ 颗不同的星星，这种情况下可以选择坐标 $1$ 到 $9$ 的区间。 第 $3$ 个测试用例，不管怎么选区间，所有的星星都会被归为 1 颗。 ### 约束条件 - $T \geq 1$ - $1 \leq N \leq 200\,000$ - $0 \leq X_1 < \dots < X_N \leq 10^8$ - $1 \leq A_i \leq 10^8$ - $T$ 组数据中，所有 $N$ 之和不超过 $200\,000$ - 所有输入均为整数。 由 ChatGPT 5 翻译