← 返回题目列表

AtCoder · arc035_d

D. 高桥君和马拉松路线

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

問題文

高桥君是马拉松赛事的组织者,正在为即将举行的马拉松赛事制定计划。 高桥君住在一个东西南北延伸的小镇里。 10^6 有一条主干道,从西边的道路由北向南延伸。 x 南路及东西延伸路 y 第条路相交的路口 表示为 (x,y) 。

为了更轻松地创建马拉松路线,我们将路径设置为仅向东或向北。 高桥君是一个可以用来测量参与者在马拉松赛道上的时间的地方。N 检查点 我决定 (p_i,q_i) 。

在高桥君的镇上,赛道上不同路线的数量很重要,因为每个参与者都想在马拉松比赛中采取不同的路线。 由于需要测量时间而设置检查点 来自 u 的检查点 当将马拉松路线设置为 v (u < v) 时,u≦i≦v 检查点 i 参与者必须经历一切。

所以,高桥君做了以下事情: Q 疑问需要得到解答。

  1. k_j 检查点位置 更改为 (a_j,b_j) 。
  2. 检查点 最多 l_{1j} 的检查点 当将马拉松路线设置为 r_{1j} 的不同路线和检查点总数 确定 l_{2j} 的检查点 当将马拉松路线设置为 r_{2j} 之前的不同路线总数中哪一个较大。然而,较多的路线是 2 保证大于两倍。

请编写一个程序来帮助高桥君。


入力

输入将以以下格式从标准输入给出。

N
p_1 q_1
p_2 q_2
:
p_N q_N
Q
t_1 …
:
t_Q …
  • 1 行包含一个表示检查点数量的整数。 N (2 ≦ N ≦ 2*10^5) 给出。
  • 2 从线 N 行包含一个表示检查点位置的整数。 p_i, q_i(1 ≦ p_i, q_i ≦ 10^6) 用空格分隔。
  • N+2 行包含一个表示查询数量的整数。 Q( 1 ≦ Q ≦ 2*10^5) 给出。
  • N+3 从行 Q 行给出了查询。 表示第t_j 为 j 个查询的类型。 当
  • t_j = 1 时,该行 k_j, a_j, b_j(1 ≦ k_j ≦ N, 1 ≦ a_j, b_j ≦ 10^6) 用空格分隔。
  • t_j = 2 时,该行 l_{1j}, r_{1j}, l_{2j}, r_{2j} (1 ≦ l_{1j} < r_{1j} ≦ N, 1 ≦ l_{2j} < r_{2j} ≦ N ) 用空格分隔。
  • 任何 i(1 ≦ i ≦ N-1) 的检查点 i 的检查点 当将马拉松路线设置为 i+1 的路径始终是(即使检查点位置在查询中发生变化)1 保证存在一个。此外,检查点位置不重叠。

部分点

针对此问题设置了部分分数。

  • 30 在点的测试用例中, 查询的答案2≦N≦1,000, 1≦Q≦1,000 符合。

出力

種類 2 查询的答案 1 按照查询中给出的顺序输出每一行。检查站 来自 l_{1j} 的检查点 当有更多前往 r_{1j} 的路线时 FIRST,检查点 输出 l_{2j} 的检查点 当将马拉松路线设置为 r_{2j} 的路线时 SECOND 。 在第

不要忘记最后的换行符。


入力例1

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

出力例1

FIRST
SECOND
FIRST

1 个查询中,检查点 前往1 的检查点 当将马拉松路线设置为3 的路线数量如下: 5 一。

检查点 最多 3 的检查点 当将马拉松路线设置为 4 的路线数量如下: 2 一。

因此, 输出FIRST 。 对于第

2 个查询,路线数量为 5 和 10 所以, 第SECOND 。 对于第

3 个查询处的检查点 2 的位置改变后,4 个查询,路线数量为 10 和 2 所以, 第FIRST 。 对于第


入力例2

4
1 1
100 100
101 102
199 199
3
2 1 2 2 3
2 1 2 2 4
2 1 2 3 4

出力例2

FIRST
FIRST
FIRST

请注意,比较的数字可能非常大。