103686: [Atcoder]ABC368 G - Add and Multiply Queries

Problem Statement

You are given sequences of positive integers $A$ and $B$ of length $N$. Process $Q$ queries given in the following forms in the order they are given. Each query is of one of the following three types.

• Type $1$: Given in the form 1 i x. Replace $A_i$ with $x$.
• Type $2$: Given in the form 2 i x. Replace $B_i$ with $x$.
• Type $3$: Given in the form 3 l r. Solve the following problem and print the answer.
  • Initially, set $v = 0$. For $i = l, l+1, ..., r$ in this order, replace $v$ with either $v + A_i$ or $v \times B_i$. Find the maximum possible value of $v$ at the end.

It is guaranteed that the answers to the given type $3$ queries are at most $10^{18}$.

Constraints

• $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$
• For type $1$ and $2$ queries, $1 \leq i \leq N$.
• For type $1$ and $2$ queries, $1 \leq x \leq 10^9$.
• For type $3$ queries, $1 \leq l \leq r \leq N$.
• For type $3$ queries, the value to be printed is at most $10^{18}$.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\cdots$ $A_N$
$B_1$ $B_2$ $\cdots$ $B_N$
$Q$
$query_1$
$query_2$
$\vdots$
$query_Q$

Here, $query_i$ is the $i$-th query, given in one of the following formats:

$1$ $i$ $x$

$2$ $i$ $x$

$3$ $l$ $r$

Output

Let $q$ be the number of type $3$ queries. Print $q$ lines. The $i$-th line should contain the answer to the $i$-th type $3$ query.

Sample Input 1

3
3 2 4
1 2 2
3
3 1 3
1 1 1
3 1 3

Sample Output 1

12
7

For the first query, the answer is $((0 + A_1) \times B_2) \times B_3 = 12$. For the third query, the answer is $((0 + A_1) + A_2) + A_3 = 7$.

Sample Input 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

Sample Output 2

46080
69840
27648
1728

问题陈述

给定长度为$N$的正整数序列$A$和$B$。按给定的顺序处理$Q$个查询。每个查询都是以下三种类型之一。

• 类型$1$：以1 i x的形式给出。将$A_i$替换为$x$。
• 类型$2$：以2 i x的形式给出。将$B_i$替换为$x$。
• 类型$3$：以3 l r的形式给出。解决以下问题并打印答案。
  • 初始时，设置$v = 0$。按照$l, l+1, ..., r$的顺序，将$v$替换为$v + A_i$或$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