시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 256 MB | 287 | 135 | 113 | 49.130% |
You are given an integer sequence $a_0, a_1, \ldots, a_{N-1}$.
You have to perform $Q$ queries, each query is one of the following:
l r x
: for each $i$ between $l$ and $r$ inclusively, $a_i = a_i + x$.l r x
: for each $i$ between $l$ and $r$ inclusively $a_i = {\rm floor}(a_i / x)$, where ${\rm floor}(y)$ is the biggest integer that is not greater than $y$.l r x=0
: print ${\rm max}(a_l, a_{l+1}, \ldots, a_r)$.Input is given in the following format:
$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$
$\ldots$
$t_Q$ $l_Q$ $r_Q$ $x_Q$
For each MAX query, print ${\rm max}(a_l, a_{l+1}, ..., a_r)$.
All input values are integers, $1 \leq N, Q \leq 200\,000$, $0 \leq a_i \leq 10^8$, $t_i = 0, 1, 2$, $0 \leq l_i \leq r_i \leq N-1$, $1 \leq x_i \leq 1000$ if $t_i \neq 2$, $x_i=0$ if $t_i=2$.
5 7 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
5 12 3 2 3
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
1 1 1
10 20 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 1 1 3 7 2 2 2 0 2 3 5 0 0 1 4 2 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 2 1 6 0 0 1 1 7 1 4 8 10 2 0 9 0 1 5 6 1
3 26 13 40 30 52
For Sample 1,
${\rm max}(1, 2, 3, 4, 5) = 5$
$1, 2, 3, 4, 5 \to 11, 12, 3, 4, 5$
${\rm max}(11, 12, 3, 4, 5) = 12$
${\rm max}(3) = 3$
$11, 12, 3, 4, 5 \to 2, 3, 3, 4, 5$
${\rm max}(2) = 2$
${\rm max}(3) = 3$