#P12681. [集训队互测2025day11]序列

    ID: 11867 传统题 3000ms 512MiB 尝试: 3 已通过: 2 难度: 8 上传者: 标签>CF2500省选/NOI-根号分块整块懒标记差分标记区间修改前后缀最值一维前缀和二分查找高精度加法

[集训队互测2025day11]序列

题目描述

已知一个序列 aa 和一个初值为 00 的序列 bb,你需要进行下面三种操作:

  • 1 x y:将 axa_x 修改为 yy。
  • 2 l r:对于所有的 i∈[l,r]i \in [l, r],将 bib_i 加上 max⁡j=liaj\max_{j=l}^{i} a_j。
  • 3 l r:求 ∑i=lrbi\sum_{i=l}^{r} b_i。

输入格式

第一行包含两个正整数 n,mn, m,分别表示序列 aa 的长度和操作次数。

第二行包含 nn 个整数 a1,a2,⋯ ,ana_1, a_2, \cdots, a_n,表示序列 aa。

接下来 mm 行,每行行首有一个整数 opop,表示操作类型,接下来两个整数表示操作参数。

输出格式

对于 op=3op = 3 的操作,输出一行包含一个整数,表示这个询问的答案。

样例输入 1

5 5
2 1 4 3 5
2 1 3
2 4 3
1 2 3
3 1 3
3 2 5

样例输出 1

8
6

样例输入 2

10 10
5 6 10 3 6 7 10 10 1 10 
2 2 4
1 10 7
3 2 8
2 4 5
1 8 2
3 2 2
2 8 9
2 1 2
1 2 10
3 2 3

样例输出 2

26
6
22

数据范围

对于 100%100\% 的数据,保证 1≤n,m≤5×1051 \le n, m \le 5 \times 10^5, 1≤l≤r≤n1 \le l \le r \le n,1≤x≤n1 \le x \le n,1≤ai,y≤1091 \le a_i, y \le 10^9。

子任务编号$n, m \le$分值特殊性质
$1$$1000$$5$无
$2$$10^5$$15$
$3$$2 \times 10^5$$20$
$4$$5 \times 10^5$$20$当 $op = 2$ 时,$l = 1$。
$5$$20$$op \ne 1$
$6$$20$无