1012. 最后一次相遇

题目描述

河灵有一条无限长的数轴。初始时，数轴上有 n 个小球，第 i 个小球的初始坐标为 xi，速度为 vi。

从时刻 0 开始，所有小球同时出发，并始终做匀速直线运动。也就是说，一个初始坐标为 x 速度为 v 的小球，在时刻 t (t ≥ 0) 的坐标为

x + v ⋅ t。若两个不同的小球在某个时刻 t (t ≥ 0) 位于同一坐标，则认为它们在时刻 t 相遇。小球之间的运动相互独立，即使两个小球在某一时刻相遇，它们之后仍会保持原来的速度继续运动。河灵明白，相遇即是缘分，所以他想请你回答 Q 次询问。每次询问相互独立，形式如下：

• l r a b：加入一个初始坐标为 a 速度为 b 的临时小球，该小球同

样从时刻 0 开始始终做匀速直线运动。求临时小球与编号在 [l, r]内的小球发生相遇的所有时刻中的最大值。特别地，若临时小球与编号在 [l, r] 内的小球均没有相遇，则输出 -1。每次询问结束后，临时小球将会被移除，不会影响其他询问。保证不会出现两个初始坐标与速度均相同的小球，所以任意两个小球至多只会相遇一次。

输入格式

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 T (

1 ≤ T ≤ 5 × 105 )，表示数据组数。对于每组测试数据：第一行两个正整数 n, Q (1 ≤ n, Q ≤ 105 )，表示初始小球的个数以及询问的个数。

接下来 n 行，第 i 行两个整数 xi, vi (−109 ≤ xi, vi ≤ 109 )，表示第 i

个小球的初始坐标与速度。接下来 Q 行，每行四个整数 l, r, a, b (1 ≤ l ≤ r ≤ n, −109 ≤ a, b ≤

109 )，表示一次询问。保证不会出现两个初始坐标与速度均相同的小球。具体地：

• 不存在 1 ≤ i < j ≤ n 满足 xi = xj 且 vi = vj。

• 对于所有询问 l, r, a, b，不存在 1 ≤ i ≤ n 满足 xi = a 且 vi = b

。保证所有测试数据中 n 之和与 Q 之和均不超过 5 × 105。

输出格式

对于每组测试数据：输出共 Q 行，第 i 行表示第 i 次询问的答案。对于每次询问：若临时小球与编号在 [l, r] 内的小球均没有相遇，则输出一个 -1。否则，可以证明答案是一个有理数。你需要输出一个既约分数 x/y，满足 y > 0 且 gcd(x, y) = 1。

样例输入

2
5 4
0 1
10 -1
5 0
-4 2
3 3
1 5 0 0
1 3 20 1
2 5 3 1
1 4 -2 4
10 10
17 -3
-7 11
-7 -18
13 -10
-2 18
-18 8
4 -18
19 19
-16 3
-8 16
3 8 -1 -18
1 3 -8 20
8 10 1 4
2 6 2 -7
4 4 -9 -7
4 5 13 13
3 6 -14 6
8 8 2 4
3 8 18 -13
3 9 -11 16

样例输出

10/1
-1
7/1
12/5
17/26
25/23
3/4
11/3
22/3
3/1
2/1
-1
12/7
12/13

提示

对于第一组测试数据：使用 −1 表示未相遇。-

询问 1 的临时小球初始坐标为 0 速度为 0，与小球 1 ∼ 5 的相遇时间分别为 0, 10, −1, 2, −1，故答案为 10/1。

• 询问 2 的临时小球初始坐标为 20 速度为 1，与小球 1 ∼ 3 均没有相遇，故答案为 -1。

• 询问 3 的临时小球初始坐标为 3 速度为 1，与小球 2 ∼ 5 的相遇时间分别为 72, 2, 7, 0，故答案为 7/1。

• 询问 4 的临时小球初始坐标为 −2 速度为 4，与小球 1 ∼ 4 的相遇时间分别为 23, 12, 7, −1，故答案为 12/5。5 4

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第2场）