题目详情题解（0）讨论（0）提交记录（0）

AT_abc368_g.[ABC368G] Add and Multiply Queries

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定两个长度为 $ 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, \dots, r $ 进行操作，每次操作将 $ v $ 替换为 $ v + A_i $ 或 $ v \times B_i $。求最终能得到的 $ v $ 的最大值。
      需要注意的是，输入中类型 $ 3 $ 的查询的答案保证在 $ 10^{18} $ 以下。

输入格式

输入从标准输入按以下格式给出：

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N
Q
query_1
query_2
...
query_Q

其中 $ query_i $ 是第 $ i $ 个查询，可以是以下三种格式之一：

1 i x
2 i x
3 l r

输出格式

设类型 $ 3 $ 的查询个数为 $ q $，则输出 $ 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

  • 输入#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

说明/提示

制約

  • $ 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} $ 以下

输入解题思路，AI测评打分。不知道怎么写?

首页