H - 区間加算・区間最小値 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点: 100 点

問題文

長さ N の数列 A = (a_0, a_1, \ldots, a_{N-1}) があります。Q 個のクエリが与えられるので、これらを順に処理してください。

  • クエリ 1: l, r, x が与えられるので、a_l, a_{l+1}, \ldots, a_{r-1} に x を足す
  • クエリ 2: l, r が与えられるので、\min( a_l, a_{l+1}, \ldots, a_{r-1} ) を求める

入力

入力は以下の形式で標準入力から与えられます。

N
a_0 a_1 \ldots a_{N-1}
Q
\mathrm{Query}_0
\vdots
\mathrm{Query}_{Q-1}

\mathrm{Query}_i は以下の形式で与えられます。

  • クエリ 1 の場合
1 l r x
  • クエリ 2 の場合
2 l r

出力

クエリ 2 それぞれについて、答えを 1 行に 1 つずつ、順に出力してください。

制約

  • 1 \leq N \leq 100{,}000
  • 1 \leq a_i \leq 10^{9}
  • 1 \leq Q \leq 100{,}000
  • 0 \leq l_i < r_i \leq N

  • 1 \leq x_i \leq 10^{9}

入力例 

6
5 1 8 2 1 5
3
2 0 4
1 1 4 5
2 0 3

出力例 

1
5

  • 1 個目のクエリでは、\min(a_0, a_1, a_2, a_3) = \min(5, 1, 8, 2) = 1 を出力します。
  • 2 個目のクエリでは、a_1, a_2, a_3 それぞれに 5 を足します。これにより、数列は A = (5, 6, 13, 7, 1, 5) に変化します。
  • 3 個目のクエリでは、\min(a_0, a_1, a_2) = \min(5, 6, 13) = 5 を出力します。