AT_aalc001_i 連続部分列

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`: Choose between $ 0 $ and $ 2 $ nonempty contiguous subsequences of the sequence $ (A_l,A_{l+1},\ldots,A_r) $ that do not share any elements. Print the maximum possible sum of the elements in the chosen contiguous subsequences. Here, a nonempty contiguous subsequence of $ (A_l,A_{l+1},\ldots,A_r) $ is a sequence $ (A_s,A_{s+1},\ldots,A_t) $ obtained by choosing integers $ s,t $ satisfying $ l\leq s\leq t\leq r $ . Also, when choosing $ 2 $ contiguous subsequences, the positions they contain must not overlap.

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 the first type $ 2 $ query, choosing $ (A_3,A_4,A_5)=(3,-1,2) $ and $ (A_7)=(5) $ gives a sum of $ 9 $ . This is the maximum. For query $ 4 $ , $ A $ is $ (4,-5,3,10,2,-6,5) $ . In this case, choosing $ (A_3,A_4,A_5) $ and $ (A_7) $ gives a sum of $ 20 $ , which is the maximum. For query $ 7 $ , choosing no contiguous subsequences gives a sum of $ 0 $ . This is the maximum. ### Constraints - $ 1\leq N\leq 10^5 $ - $ 1\leq Q\leq 10^5 $ - $ -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\leq r\leq N $ - All numerical values in the input are integers.