| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 256 MB | 545 | 222 | 185 | 47.436% |
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$