#5089. 【模板】大帅の区间最大值

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: long_hao

题目描述

蟹蟹 laffey 教我怎么造数据

如题,在有区间修改的情况下维护区间的最大最小值。

因为没找到类似的题目所以自己造了一个。

笨笨的大帅在考试考了ST表之后才知道一种惊天骇俗的算法——线段树(实际上是码量太大了之前懒得写),于是乎他开始了敲敲敲,但是他发现了一个问题,他并没有找到一道同时拥有区间修改和查询区间最大值最小值的题目,他就去做了线段树3,发现自己就是个彩笔,直到他看到了这道题,他觉得自己又行了。

大帅最近写线段树做梦都在维护区间最大值,但是他的代码水平实在太低了,看不下去的你准备帮帮他。

2022-8-19 添加该题目

2022-8-19 该题目名字被篡改,原名:[模板]线段树动态维护区间最大最小值

输入格式

第一行给出一个 n m

第二行输入长度为 n 的数组分别是 a_i

接下来 m 行,输入 num 做出以下规定

  • 如果 num 1 ,输入 x y z ,表示在 x y 区间中每个数字添加 z
  • 如果 num 2 ,输入 x y ,表示在 x y 区间中查询区间最大值
  • 如果 num 3 ,输入 x y ,表示在 x y 区间中查询区间最小值

输出格式

回答查询,输出的时候记得带换行就行

样例

样例输入

3 3
6 5 3 
1 1 3 2
2 1 3
3 2 2

样例输出

8
7

数据范围与提示

对于30%的数据,满足 n\leq100 m\leq100

对于50%的数据,满足 n\leq1000 m\leq1000

对于80%的数据,满足 n\leq10000 m\leq10000

对于100%的数据,满足 0\leq n\leq200000 0\leq m\leq200000 0\leq a_i \leq1e4