← 返回题目列表

AtCoder · jag2018summer_day2_i

I. 添加 DIV 最大恢复

中文机器翻译题面 查看原题

分数: 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