← 返回题目列表

AtCoder · abc368_g

G. 加法和乘法查询

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

分数: 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