天梯赛赛制测试赛

Problem E. 吉老师线段树

这是一道模板题。你需要维护一个序列 a

  • 0 l r t \forall l\le i\le r, a_i=\min(a_i,t)
  • 1 l r 输出区间 [l,r] 最大值
  • 2 l r 输出区间和

输入

输入一行两个整数 n,m(n\le 10^5,m\le10^5)

接下来输入一行 n 个整数 a_i(1\le a_i\le 10^9)

接下来输入 m 行,每行格式如上所述 (1\le l\le r\le n,1\le t\le 10^9)

输出

对于每个操作 1 或操作 2 ,输出一行一个整数代表答案

样例

标准输入 复制文本
5 6
1 2 3 4 5
0 1 4 2
1 2 4
2 1 4
0 1 5 6
1 1 5
2 4 5
标准输出 复制文本
2
7
5
7

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 2
通过 1

A B C D E