S - Absolute Value Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 5 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

クエリを Q 個処理してください。クエリは以下の 2 種類のいずれかです。

  • 1 i x：A_i を x に変更する。
  • 2 l r：整数 m と整数列 (i_1,i_2,\ldots,i_m) を 3 \leq m かつ l \leq i_1 \lt i_2 \lt \cdots \lt i_m \leq r を満たすように選べるとき、次の値の最大値を出力する。

\[ \sum_{k=1}^{m-2} \left|A_{i_k}+2A_{i_{k+1}}+3A_{i_{k+2}}\right| \]

制約

  • 1 \leq N \leq 5 \times 10^4
  • 1 \leq Q \leq 5 \times 10^4
  • -10^9 \leq A_i \leq 10^9
  • 1 種類目のクエリについて、1 \leq i \leq N, -10^9 \leq x \leq 10^9
  • 2 種類目のクエリについて、1 \leq l \lt r \leq N, r-l \geq 2
  • 入力される数値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
A_1 A_2 \ldots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは以下のいずれかの形式で与えられる。

1 i x

2 l r

出力

2 種類目のクエリの個数を q として、q 行出力せよ。j 行目には、j 番目の 2 種類目のクエリに対する答えを出力せよ。

入力例 1

5 5
1 -2 3 -1 2
2 1 3
2 1 5
1 2 4
2 1 3
2 2 5

出力例 1

6
16
18
16

1 番目のクエリでは m=3,(i_1,i_2,i_3)=(1,2,3) とする以外に選び方はなく、求める値は 6 です。

2 番目のクエリでは m=4,(i_1,i_2,i_3,i_4)=(1,2,3,5) と選ぶと、求める値は 16 になります。これが最大値です。

3 番目のクエリによって A_2 は 4 に変更されます。

入力例 2

6 4
-3 1 -4 1 -5 9
2 1 6
1 4 -2
2 2 5
2 3 6

出力例 2

52
36
38

入力例 3

3 3
-1000000000 -1000000000 -1000000000
2 1 3
1 2 1000000000
2 1 3

出力例 3

6000000000
2000000000

Score: 5 points

Problem Statement

You are given a sequence of integers A=(A_1,A_2,\ldots,A_N) of length N.

Process Q queries. Each query is of one of the following 2 types:

  • 1 i x: Change A_i to x.
  • 2 l r: Over all choices of an integer m and a sequence of integers (i_1,i_2,\ldots,i_m) satisfying 3 \leq m and l \leq i_1 \lt i_2 \lt \cdots \lt i_m \leq r, print the maximum value of the following expression:

\[ \sum_{k=1}^{m-2} \left|A_{i_k}+2A_{i_{k+1}}+3A_{i_{k+2}}\right| \]

Constraints

  • 1 \leq N \leq 5 \times 10^4
  • 1 \leq Q \leq 5 \times 10^4
  • -10^9 \leq A_i \leq 10^9
  • For type 1 queries, 1 \leq i \leq N, -10^9 \leq x \leq 10^9
  • For type 2 queries, 1 \leq l \lt r \leq N, r-l \geq 2
  • All numerical values in the input are integers.

Input

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

N Q
A_1 A_2 \ldots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in one of the following formats:

1 i x

2 l r

Output

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

Sample Input 1

5 5
1 -2 3 -1 2
2 1 3
2 1 5
1 2 4
2 1 3
2 2 5

Sample Output 1

6
16
18
16

For query 1, the only choice is m=3,(i_1,i_2,i_3)=(1,2,3), and the value sought is 6.

For query 2, choosing m=4,(i_1,i_2,i_3,i_4)=(1,2,3,5) gives a value of 16. This is the maximum.

Query 3 changes A_2 to 4.

Sample Input 2

6 4
-3 1 -4 1 -5 9
2 1 6
1 4 -2
2 2 5
2 3 6

Sample Output 2

52
36
38

Sample Input 3

3 3
-1000000000 -1000000000 -1000000000
2 1 3
1 2 1000000000
2 1 3

Sample Output 3

6000000000
2000000000