Add and Multiply Queries

题目描述

给定长度为 $N$ 的正整数序列 $A$ 和 $B$。按给定顺序处理 $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$ 或 $v \times B_i$ 中的一个。求最终 $v$ 的最大可能值。

保证所有给定的类型 $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$ 查询的答案。

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

12
7

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

46080
69840
27648
1728

提示

$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}$。对于第一个查询，答案是 $((0 + A_1) \times B_2) \times B_3 = 12$。 对于第三个查询，答案是 $((0 + A_1) + A_2) + A_3 = 7$.

标签: AtCoder|abc368G

来源

AtCoder|abc368G