配点 : 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)
小課題
- (100 点) Q = 1
- (150 点) T_j = 1, L_j = 1, R_j = N \ (1 \leq j \leq Q)
- (350 点) T_j = 2, L_j = 1, R_j = N \ (1 \leq j \leq Q)
- (200 点) T_j = 1, V_j = A_{P_j} \ (1 \leq j \leq Q)
- (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 的约束。