← 返回题目列表

AtCoder · abc432_e

H. 夹钳

中文机器翻译题面 查看原题

分数: 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