← 返回题目列表

AtCoder · pakencamp_2022_day2_h

H. 哈巴图

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

配点 : 900 点

問題文

PA 实验室成员排队 N 人们在排队。从左边开始 i \ (1 \leq i \leq N) 会员 我们称之为 i 。现任成员 i 的计算机技能是 A_i 。相邻的俱乐部成员之间有一个友谊指数, 1 \leq i \leq N - 1 现有成员 i 和成员 i + 1 的友谊等级是 B_i 。这里 B_i 是不同的。

PA 实验室成员喜欢派系斗争。一般来说,派系冲突是被禁止的,但我们想一下,如果发生派系冲突,会发生什么。 当

人 l, l + 1, \cdots , r \ (1 \leq l \leq r \leq N) 开始派系战争时,会发生以下情况:

  • 始,派系 l, l + 1, \cdots ,r 存在且成员 i \ (l \leq i \leq r) 是一个派系 属于 i 。其他成员不属于任何派系。
  • 派閥 a, b \ (l \leq a < b \leq r) 的友谊级别定义如下。

    在任何时间点,派系 a 人 i 属于,派系 b 人 i+1 属于 i 最多是 1 可以证明有两个。友谊的层次是这样的 如果 i 不存在 -10^{100} 如果存在 B_i 。

  • 派系 1 重复以下事件,直到发生一个事件。

    友谊等级最高 考虑 2 派閥 a, b \ (a < b) 。属于每个派别的人的计算机技能的总和。 s, t 。此时 s \geq t 奈良派 所有属于 b 的人都是派系。 将隶属关系更改为 a 将隶属关系更改为 s < t 奈良派 所有属于 a 的人都是派系。 将隶属关系更改为 b 。此外,不再有任何人属于他们的派系将会消失。

PA Lab的活动将从明天开始。 Q 由于俱乐部在白天活跃,俱乐部成员的计算机技能和友好程度经常变化。具体来说, j \ (1 \leq j \leq Q) 天发生以下变化:

  • T_j = 1 ,成员 P_j 的计算机技能 V_j 。
  • T_j = 2 ,成员 P_j 和成员 P_j + 1 之间的友谊程度 V_j 。

然而,在任何一个时间点,保证成员之间的友好程度都会有所不同。

派系太郎,喜欢想象派系冲突,每天都会进行关于派系冲突的思想实验。具体来说, j \ (1 \leq j \leq Q) 归根结底,会员们 当 L_j, L_j + 1, \cdots ,R_j 开始派系战争时找到最后剩下的派系。

找出每个思想实验的结果。

制約

  • 所有输入均为整数
  • 在任何时间点,友谊的程度都会有所不同。
  • 2 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
  • 1 \leq B_i \leq 10^9 \ (1 \leq i \leq N - 1)
  • T_j \in \{1, 2\} \ (1 \leq j \leq Q)
  • T_j = 1 保证可以在 1 \leq P_j \leq N \ (1 \leq j \leq Q)
  • T_j = 2 保证可以在 1 \leq P_j \leq N - 1 \ (1 \leq j \leq Q)
  • 1 \leq V_j \leq 10^9 \ (1 \leq j \leq Q)
  • 1 \leq L_j \leq R_j \leq N \ (1 \leq j \leq Q)

小課題

  1. (100 点) Q = 1
  2. (150 点) T_j = 1, L_j = 1, R_j = N \ (1 \leq j \leq Q)
  3. (350 点) T_j = 2, L_j = 1, R_j = N \ (1 \leq j \leq Q)
  4. (200 点) T_j = 1, V_j = A_{P_j} \ (1 \leq j \leq Q)
  5. (100 点)无附加约束

入力

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

N
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_{N - 1}
Q
T_1 P_1 V_1 L_1 R_1
T_2 P_2 V_2 L_2 R_2
\vdots
T_Q P_Q V_Q L_Q R_Q

出力

Q 行。j \ (1 \leq j \leq Q) 行中, j 在派系太郎第一天的思想实验中,最后剩下的派系是 当 a 什么时候 a 。


入力例 1

5
5 9 9 7 9
6 7 3 4
3
1 4 7 4 5
2 4 10 1 3
1 1 6 1 3

出力例 1

5
2
2

为例 1 考虑戴的思想实验。1 会员在一天结束时 4, 5 的计算机技能是 7, 9 。因此, 1 在当天的思想实验中,最后剩下的就是一个派系。 5 。

此输入/输出示例满足子任务 5 的约束。


入力例 2

8
14 10 12 20 18 1 6 13
2 16 1 3 4 12 11
5
1 2 3 1 8
1 3 8 1 8
1 1 4 1 8
1 7 15 1 8
1 4 19 1 8

出力例 2

8
8
8
7
7

此输入/输出示例满足子任务 2 和 5 的约束。


入力例 3

8
10 17 13 17 16 1 19 8
11 1 9 4 2 12 10
5
2 2 7 1 8
2 4 15 1 8
2 3 5 1 8
2 2 13 1 8
2 6 14 1 8

出力例 3

4
4
2
2
2

此输入/输出示例满足子任务 3 和 5 的约束。


入力例 4

8
11 11 2 2 10 5 2 15
9 1 10 19 7 14 20
3
1 1 11 8 8
1 1 11 4 6
1 1 11 2 6

出力例 4

8
5
5

此输入/输出示例满足子任务 4 和 5 的约束。


入力例 5

20
30 95 72 93 69 100 45 51 7 19 40 61 73 51 98 71 25 51 15 91
20 69 94 58 63 70 80 17 66 10 83 48 40 86 23 67 60 44 96
6
2 9 71 6 15
1 2 46 11 15
1 6 15 6 19
2 8 8 1 13
2 8 26 6 18
1 9 31 5 14

出力例 5

12
12
12
4
12
8

此输入/输出示例满足子任务 5 的约束。