AT_aalc001_s 絶対値

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| \\\]

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 $

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 Explanation 1 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 $ . ### 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.