← 返回题目列表

AtCoder · tenka1_2016_qualB_d

D. 向 Tenkaichi 序列发送查询

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

配点 : 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] :第一次查询后
  • [-10, -9, -18] : 第二次查询后
  • [-10, 11, 2] :第三次查询后

研究查询的输出如下

  • 第一个探测查询输出 min(0, 10)=0
  • 第二个探测查询是 min(0, 10, -10)=-10 输出(21:18修正)将输出
  • 第三个探测查询输出 min(-9, 11)=-9
  • 第四个探测查询输出 min(1, 11)=1
  • 第五次探测查询输出 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