分数: 450 点
问题陈述
给你一个整数序列 A=(A_1, A_2, \dots, A_N) 长度 N.
你被给予 Q 查询,您应按顺序处理。 每个查询均采用以下格式之一:
1 x y:更改值 A_x to y.2 l r:查找值 \displaystyle \sum_{1\leq i\leq N} \max(l, \min(r, A_i)).
约束
- 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
- 所有输入均为整数。
输入
输入由标准输入按以下格式给出:
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-th 查询,并以下列格式之一给出:
1 x y
2 l r
输出
让 K 是第二类查询的数量。输出 K 行。 的 i- 第行 (1\leq i \leq K)应包含以下问题的答案 i第二类型的第一个查询。
示例输入 1
3 4 4 3 2 1 1 7 2 3 5 1 2 0 2 4 2
示例输出 1
11 12
最初, A=(4,3,2).
- 第一个查询:更改值 A_1 to 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 to 0. A 变为 (7,0,2).
- 第四个查询:输出 \max(4, \min(2, 7))+\max(4, \min(2, 0))+\max(4, \min(2, 2))=4+4+4=12.
示例输入 2
8 10 320 578 244 604 145 839 156 857 2 400 556 1 5 168 2 254 62 2 145 301 1 1 23 1 3 0 2 413 758 2 297 613 1 8 451 2 598 692
示例输出 2
3824 2032 2073 4350 3596 4884