AT_abc432_e [ABC432E] Clamp

長さ $ N $ の整数列 $ A=(A_1, A_2, \dots, A_N) $ が与えられます。 $ Q $ 個のクエリが与えられるので、順に処理してください。 各クエリは以下のいずれかの形式です。 - `1 x y` : $ A_x $ の値を $ y $ に変更する。 - `2 l r` : $ \displaystyle \sum_{1\leq i\leq N} \max(l, \min(r, A_i)) $ の値を求める。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ \text{query}_1 $ $ \text{query}_2 $ $ \vdots $ $ \text{query}_Q $ ここで、 $ \text{query}_i\ (1\leq i\leq Q) $ は $ i $ 番目のクエリを表し、以下のいずれかの形式で与えられる。 > $ 1 $ $ x $ $ y $ > $ 2 $ $ l $ $ r $

$ 2 $ 種類目のクエリの個数を $ K $ として、 $ K $ 行出力せよ。 $ i $ 行目 ( $ 1\leq i \leq K $ ) には、 $ 2 $ 種類目のクエリのうち $ i $ 個目のものに対する答えを出力せよ。

### Sample Explanation 1 はじめ、 $ A=(4,3,2) $ です。 - $ 1 $ 番目のクエリ： $ A_1 $ の値を $ 7 $ に変更します。 $ A=(7,3,2) $ となります。 - $ 2 $ 番目のクエリ： $ \max(3, \min(5, 7))+\max(3, \min(5, 3))+\max(3, \min(5, 2))=5+3+3=11 $ を出力します。 - $ 3 $ 番目のクエリ： $ A_2 $ の値を $ 0 $ に変更します。 $ A=(7,0,2) $ となります。 - $ 4 $ 番目のクエリ： $ \max(4, \min(2, 7))+\max(4, \min(2, 0))+\max(4, \min(2, 2))=4+4+4=12 $ を出力します。 ### Constraints - $ 1\leq N \leq 5\times 10^5 $ - $ 1\leq Q \leq 2\times 10^5 $ - $ 0\leq A_i \leq 5\times 10^5 $ - $ 1 $ 種類目のクエリについて、 - $ 1\leq x\leq N $ - $ 0\leq y \leq 5\times 10^5 $ - $ 2 $ 種類目のクエリについて、 - $ 0\leq l,r \leq 5\times 10^5 $ - 入力は全て整数