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$

设 $K$ 为第二种类型查询的个数。输出共 $K$ 行，第 $i$ 行（$1\leq i\leq K$）为第 $i$ 个第二种类型查询的答案。

### 样例解释 1 初始时 $A=(4,3,2)$。 - 第一个查询：将 $A_1$ 改为 $7$，$A$ 变为 $(7,3,2)$。 - 第二个查询：输出 $\max(3, \min(5, 7))+\max(3, \min(5, 3))+\max(3, \min(5, 2))=5+3+3=11$。 - 第三个查询：将 $A_2$ 改为 $0$，$A$ 变为 $(7,0,2)$。 - 第四个查询：输出 $\max(4, \min(2, 7))+\max(4, \min(2, 0))+\max(4, \min(2, 2))=4+4+4=12$。 ### 数据范围 - $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 \leq x \leq N$ - $0 \leq y \leq 5\times 10^5$ - 对于第二种类型的查询， - $0 \leq l,r \leq 5\times 10^5$ - 所有输入均为整数。 由 ChatGPT 5 翻译