分数: 366 分
问题陈述
在一条数轴上,高桥和青木正在玩追逐游戏。青木朝正方向跑去,高桥追了上去。
它们的速度随时间变化 N 秒。最初,一个 速度表 给出 长度 N ,其中 i第一个条目 (1 \leq i \leq N) 指定 Aoki 的速度 A_i 和高桥的速度 B_i.
时间从 0。对于每个非负整数 s,期间 1- 时间的秒间隔 使用速度表的 s 到时间 s + 1, i = (s \bmod N) + 1第条目。也就是说,在这期间 1 第二,青木出招 A_i 和高桥的举动 B_i 正方向。此对应关系每次都会以相同的顺序重复 N 秒。
你处理 Q 按顺序查询。有两种类型的查询:
1 i a b:更改 i速度表的第一项,使 Aoki 的速度变为 a 高桥的速度变成 b.2 d:根据当前速度表,回答以下问题。假设在某个时间 0,高桥在坐标处 0 和青木在坐标 d,求高桥追上青木的最小非负整数时间。如果他永远追不上,则输出 -1.
在这里, 追赶 表示在某个非负整数时间 t,高桥的坐标大于或等于青木的坐标。仅在整数次时执行检查;不考虑中间两者的位置。
每个 2 查询是独立的,两者的位置不会结转到下一个查询。另一方面,对速度表所做的更改 1 查询将延续到所有后续查询。
约束
- 1 \leq N \leq 3000
- 1 \leq Q \leq 10^5
- NQ \leq 10^7
- 0 \leq A_i \leq 10^9
- 0 \leq B_i \leq 10^9
- 对于
1查询: 1 \leq i \leq N, 0 \leq a \leq 10^9, 0 \leq b \leq 10^9 - 对于
2查询: 1 \leq d \leq 10^{15} - 至少有一个
2查询 - 所有输入值均为整数
输入
N Q A_1 B_1 A_2 B_2 \vdots A_N B_N query_1 query_2 \vdots query_Q
第一行给出句点 N 和查询数量 Q。以下 N 行给出 A_i 和 B_i 上 i第行。以下 Q 行给出以下格式的查询 1 i a b or 2 d。每行上的值均以空格分隔。
输出
对于每个 2 查询,一行输出高桥追上青木的最小非负整数时间。如果他永远追不上,则输出 -1.
示例输入 1
3 5 2 5 4 3 1 2 2 1 2 4 1 2 0 6 2 8 2 20
示例输出 1
1 4 2 6
示例输入 2
3 5 2 1 0 2 1 0 2 2 2 1 1 2 5 5 2 1 2 100
示例输出 2
-1 2 -1 -1
示例输入 3
8 14 5 8 7 4 3 6 10 2 0 5 4 4 6 9 2 1 2 3 2 10 1 4 1 12 2 15 1 8 5 20 2 30 1 2 10 10 2 7 2 100 1 5 8 0 2 12 1 4 0 0 2 25 2 1
示例输出 3
1 33 5 8 4 21 4 16 1
示例输入 4
20 30 100 150 80 60 0 200 300 100 50 50 20 70 90 30 10 110 400 0 0 0 15 45 60 90 120 80 5 205 700 900 1000 500 30 31 45 40 200 250 75 125 2 1000 2 100000 1 9 0 1000 2 5000 1 16 100 1000 2 20000 1 4 0 0 1 7 0 300 2 12345 2 999999999999999 1 1 1000 0 2 100 1 10 0 1000000000 2 1000000000 1 10 1000000000 0 2 1000000000 1 15 900 700 1 20 125 75 2 7777 2 42 1 2 0 0 1 3 500 100 2 314159 1 18 0 100 2 271828 1 5 0 0 2 1000000000000000 1 12 1000000000 1000000000 2 600 2 600000
示例输出 4
-1 -1 89 156 80 6459948320415 9 10 -1 -1 9 -1 -1 -1 -1 -1
示例输入 5
1 8 1000000000 0 2 1 1 1 0 0 2 1 1 1 0 1000000000 2 1000000000000000 2 1 1 1 1000000000 1000000000 2 1
示例输出 5
-1 -1 1000000 1 -1