AT_pakencamp_2022_day2_h Habatu

パ研部员们排成一列，共有 $N$ 人。从左到右，第 $i$ $(1 \leq i \leq N)$ 位部员称为部员 $i$。当前部员 $i$ 的电脑能力为 $A_i$。相邻的部员间存在“亲密度”这一指标，对于 $1 \leq i \leq N-1$，部员 $i$ 和部员 $i+1$ 之间的亲密度为 $B_i$。所有 $B_i$ 互不相同。 パ研部员们很喜欢“派系斗争”。虽然通常禁止派系斗争，但我们来思考万一发生时会怎样。 假设编号为 $l, l+1, \cdots, r$ $(1 \leq l \leq r \leq N)$ 的人发动了派系斗争，则会发生如下事件： - 最初，存在 $l, l+1, \cdots, r$ 共 $r-l+1$ 个派系，部员 $i$ $(l \leq i \leq r)$ 隶属于派系 $i$。其他部员则不属于任何派系。 - 派系 $a, b$ $(l \leq a < b \leq r)$ 之间的亲密度定义如下：> 任何时刻能证明同一时刻仅有至多一个下标 $i$，使得部员 $i$ 属于派系 $a$，部员 $i+1$ 属于派系 $b$。若不存在此 $i$，亲密度为 $-10^{100}$；若存在，则为 $B_i$。 - 派系数量超过 $1$ 时，不断重复以下事件：> 考虑所有派系对 $(a, b)$ $(a < b)$，找到亲密度最大的那一对。设两个派系对应成员电脑能力之和分别为 $s, t$。若 $s \geq t$，则 $b$ 的所有成员全部归入派系 $a$；否则，$a$ 的所有成员全部归入派系 $b$。消灭成员为空的派系。 由于パ研活动在接下来 $Q$ 天内十分活跃，部员能力和亲密度会频繁变化。第 $j$ $(1 \leq j \leq Q)$ 天发生如下变化： - 若 $T_j=1$，则部员 $P_j$ 的电脑能力变为 $V_j$。 - 若 $T_j=2$，则部员 $P_j$ 和 $P_j+1$ 的亲密度变为 $V_j$。 无论何时都保证任意两个人之间的亲密度互不相同。 喜欢幻想派系斗争的“派系太郎”君，每日都进行派系斗争的思考实验。具体地说，每天结束时，他会设想部员 $L_j, L_j+1, \cdots, R_j$ 开始派系斗争，最终哪个派系能胜出。 请输出每次思考实验的结果。

输入通过标准输入给出，格式如下： > $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$ 的编号。

## 子任务 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 分）无其他约束 ## 样例解释 1 以第 $1$ 天为例，第 $4, 5$ 号部员的电脑能力为 $7, 9$。所以，第 $1$ 天思考实验最终胜出的派系是 $5$。 该输入输出样例满足子任务 5 的约束。 ## 样例解释 2 该输入输出样例满足子任务 2, 5 的约束。 ## 样例解释 3 该输入输出样例满足子任务 3, 5 的约束。 ## 样例解释 4 该输入输出样例满足子任务 4, 5 的约束。 ## 样例解释 5 该输入输出样例满足子任务 5 的约束。 ## 约束条件 - 所有输入均为整数。 - 任意时刻亲密度均互不相同。 - $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$ - 若 $T_j=2$，则 $1 \leq P_j \leq N-1$ - $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)$ 由 ChatGPT 5 翻译