G - Add and Multiply Queries Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 575 点

問題文

長さ N の正整数列 A, B が与えられます。以下の形式で与えられる Q 個のクエリを、与えられた順番に処理してください。クエリは次の 3 種類のいずれかです。

  • タイプ 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} 以下であることが保証されています。

制約

  • 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

出力

タイプ 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

1 番目のクエリでは、答えは ((0 + A_1) \times B_2) \times B_3 = 12 です。 3 番目のクエリでは、答えは ((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

Score : 575 points

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