琪露诺的完美算术教室 / 【模版】基础线段树
出题人太菜,暂无测试数据。
题目背景
在幻想乡,琪露诺是以 \(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\frac{\sum_{i=L}^{n} a_i}{|[L, R]|}\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}\)
相关
在下列训练计划中: