天下一プログラマーコンテスト2016予選B

D - 天下一数列にクエリを投げます


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 900

問題文

モリタ君はプログラミングコンテストの商品として長さ N の数列 a_1, a_2, ..., a_N を貰いました。

まず、この数列に対し A 個の加算クエリを行います。i 個目の加算クエリは以下のとおりです。

  • L_i, R_i, X_i が与えられるので、a_{L_i}, a_{L_i+1}, ..., a_{R_i} それぞれに X_i を足す

そのあと、B 個の調査クエリを行います。この調査クエリの結果を求めるのがあなたの仕事です。i 個目の調査クエリは以下のとおりです。

  • S_i, T_i, K_i が与えられるので、S_i 個目の加算クエリを行う直前から、T_i 個目の加算クエリを行った直後までの間での a_{K_i} の最小値を求める

制約

  • 1 ≦ N ≦ 10^5
  • 1 ≦ A, B ≦ 10^5
  • |a_i| ≦ 10^6
  • 1 ≦ L_i ≦ R_i ≦ N
  • |X_i| ≦ 10^6
  • 1 ≦ S_i ≦ T_i ≦ A
  • 1 ≦ K_i ≦ N

入力

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

N
a_1 a_2 ... a_N
A
L_1 R_1 X_1
L_2 R_2 X_2
:
L_A R_A X_A
B
S_1 T_1 K_1
S_2 T_2 K_2
:
S_B T_B K_B

出力

B 行出力する。 i 行目には i 個目の調査クエリの結果を出力する。 出力の末尾に改行を入れること。


入力例 1

3
0 1 2
3
1 2 10
1 3 -20
2 3 20
6
1 1 1
1 2 1
3 3 2
1 1 2
1 1 3
1 3 3

出力例 1

0
-10
-9
1
2
-18

数列は以下のように変動します

  • [0, 1, 2] : 最初
  • [10, 11, 2] : 1つめのクエリの後
  • [-10, -9, -18] : 2つめのクエリの後
  • [-10, 11, 2] : 3つめのクエリの後

調査クエリの出力は以下のとおりです

  • 1つめの調査クエリはmin(0, 10)=0を出力します
  • 2つめの調査クエリはmin(0, 10, -10)=-10(21:18修正)を出力します
  • 3つめの調査クエリはmin(-9, 11)=-9を出力します
  • 4つめの調査クエリはmin(1, 11)=1を出力します
  • 5つめの調査クエリはmin(2, 2)=2を出力します
  • 6つめの調査クエリはmin(2, 2, -18, 2)=-18を出力します

入力例 2

3
454314 -698320 390858
7
1 3 -916798
1 2 -927828
2 2 537269
1 1 -765412
3 3 -299727
3 3 250850
3 3 526409
7
3 5 3
1 5 1
7 7 1
6 6 1
4 5 3
3 6 3
6 6 2

出力例 2

-825667
-2155724
-2155724
-2155724
-825667
-825667
-2005677

入力例 3

7
74567 -876079 911351 746764 -924924 713268 666931
7
6 7 -318557
5 6 -349441
2 4 -629716
3 7 595329
4 7 174594
5 5 -948318
2 6 -47210
8
2 4 4
1 5 3
3 5 5
1 3 3
4 7 5
1 7 1
5 5 5
6 7 2

出力例 3

117048
281635
-1274365
281635
-1499970
74567
-679036
-1553005

Submit提出する