分数: 100 点
问题陈述
给你一个整数序列 a_0, a_1, ..., a_{N-1}.
你必须执行 Q 查询,每个查询都是以下之一:
ADD QUERY(t=0 l r x):对于每个 i 之间 l 和 r,包含,替换 a_i 与 a_i + x.DIV QUERY(t=1 l r x):对于每个 i 之间 l 和 r,包含,替换 a_i 与 {\rm floor}(a_i / x),其中 {\rm floor}(y) 是不大于的最大整数 y.MAX QUERY(t=2 l r x=0):打印 {\rm max}(a_l, a_{l+1}, ..., a_r).RESTORE QUERY(t=3 l r x=0):对于每个 i 之间 l 和 r,包含,设置 a_i 为初始值 a_i,即输入中给出的值。
约束
- 所有输入值均为整数。
- 1 \leq N, Q \leq 200,000
- 0 \leq a_i \leq 10^8
- t_i = 0, 1, 2, 3
- 0 \leq l_i \leq r_i \leq N-1
- 1 \leq x_i \leq 1000(当 t_i \neq 2, 3)
输入
输入由标准输入按以下格式给出:
N Q
a_0 a_1 ... a_{N-1}
t_1 l_1 r_1 x_1
t_2 l_2 r_2 x_2
:
t_Q l_Q r_Q x_Q
输出
对于每个 MAX QUERY,打印 {\rm max}(a_l, a_{l+1}, ..., a_r),每行一个。
示例输入 1
5 9 1 2 3 4 5 2 0 4 0 0 0 1 10 2 0 4 0 2 2 2 0 1 0 1 4 2 0 0 0 2 1 1 0 3 0 4 0 2 0 1 0
示例输出 1
5 12 3 2 3 2
- {\rm max}(1, 2, 3, 4, 5) = 5
- 1, 2, 3, 4, 5 → 11, 12, 3, 4, 5
- {\rm max}(11, 12, 3, 4, 5) = 12
- {\rm max}(3) = 3
- 11, 12, 3, 4, 5 → 2, 3, 3, 4, 5
- {\rm max}(2) = 2
- {\rm max}(3) = 3
- 阵列恢复到 1, 2, 3, 4, 5
- {\rm max}(1, 2) = 2
示例输入 2
4 7 0 1 0 1 2 0 3 0 0 0 3 1 1 0 3 2 2 0 3 0 0 0 3 1 1 0 3 2 2 0 3 0
示例输出 2
1 1 1
示例输入 3
10 23 13 1 22 8 28 18 23 9 22 27 1 3 4 5 1 8 8 8 0 3 9 5 0 2 6 3 3 0 4 0 1 1 3 7 2 2 2 0 2 3 5 0 0 1 4 2 3 0 9 0 2 0 1 0 0 3 9 8 2 1 9 0 0 8 9 5 1 5 7 7 0 3 5 7 0 7 9 7 3 3 6 0 2 1 6 0 0 1 1 7 1 4 8 10 2 0 9 0 1 5 6 1
示例输出 3
3 28 13 36 28 47