分数: 575 点
问题陈述
给定正整数序列 A 和 B 长度 N。工艺流程 Q 查询按照给出的顺序以下列形式给出。每个查询属于以下三种类型之一。
-
类型 1:以表格形式给出
1 i x。更换 A_i 与 x. -
类型 2:以表格形式给出
2 i x。更换 B_i 与 x. -
类型 3:以表格形式给出
3 l r。解决以下问题并打印答案。- 最初,设置 v = 0。对于 i = l, l+1, ..., r 按此顺序,替换 v 与任一 v + A_i or v \times B_i。找出最大可能值 v 在最后。
保证给定类型的答案 3 查询最多 10^{18}.
约束
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- 1 \leq Q \leq 10^5
- 对于类型 1 和 2 查询, 1 \leq i \leq N.
- 对于类型 1 和 2 查询, 1 \leq x \leq 10^9.
- 对于类型 3 查询, 1 \leq l \leq r \leq N.
- 对于类型 3 查询,打印的值最多为 10^{18}.
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N Q query_1 query_2 \vdots query_Q
在这里, query_i 是 i-第一个查询,以下列格式之一给出:
1 i x
2 i x
3 l r
输出
让 q 是类型的数量 3 查询。打印 q 行。的 i- 第行应包含以下问题的答案 i第类型 3 查询。
示例输入 1
3 3 2 4 1 2 2 3 3 1 3 1 1 1 3 1 3
示例输出 1
12 7
对于第一个查询,答案是 ((0 + A_1) \times B_2) \times B_3 = 12。 对于第三个查询,答案是 ((0 + A_1) + A_2) + A_3 = 7.
示例输入 2
6 65 32 12 5 8 312 4 1 3 15 16 2 6 3 2 6 3 1 5 1 5 6 2 4 9 3 2 6 3 3 5
示例输出 2
46080 69840 27648 1728