琪露诺的完美算术教室 / 【模版】基础线段树

琪露诺的完美算术教室 / 【模版】基础线段树

出题人太菜,暂无测试数据。

题目背景

在幻想乡,琪露诺是以 \(baka\) 闻名的冰之妖精。

题目描述

现在,\(baka\) 老师给了你一个长度为 \(n\) 的数列,现在你要根据 \(baka\) 的指令进行以下行动:
1. 1 L R 表示输出 \([L,R]\) 区间内的最大值。
2. 2 L R 表示输出 \([L,R]\) 区间内的最小值。
3. 3 L R 表示对 \([L,R]\) 区间内的每一个元素加该区间的最大值减区间的最小值。
4. 4 L R 表示输出 \(\bar{x}\) (注: \(\bar{x} = \lfloor\sum_{i=L}^{n} a_i / 2\rfloor\))。

输入输出格式

第一行两个正整数 \(n,m\),分别表示数列的长度 \(n\) 和 指令的个数 \(m\)。

第二行包含 \(n\) 个用空格分隔的整数,其中第 \(i\) 个数字表示数列第 \(i\) 项的初始值。

接下来 \(m\) 行,每行包含 \(3\) 个整数,表示对应的操作。

样例

输入

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

输出

5
2
5
1

数据范围

对于 \(30\%\) 的数据: \(n \le 8,m \le 10\)。

对于 \(70\%\) 的数据: \(n \le 10^3,m \le 10^4\)

对于 \(100\%\) 的数据: \(1 \le n,m \le 10^5\)

保证任意时刻数列中所有元素的绝对值之和 \(\le 10^{18}\)

信息

ID
1049
难度
(无)
分类
线段树 点击显示
标签
递交数
0
已通过
0
通过率
?
被复制
1
上传者

相关

在下列训练计划中:

模板 | Templates