火事 (Fire)

Unrated

日本語

Language

Time limit: 1500 ms
Memory limit: 256 MB
Submissions: 0
Correct: 0
Solved by: 0
AC rate: —

Statement

JOI 村には \(N\) 個の区画があり，\(1\) から \(N\) までの番号が付いている．これらの区画は番号順に一列に並んでいる．今，各区画では火事が発生しており，時刻 \(0\) における区画 \(i\) (\(1 \leqq i \leqq N\)) の火の強さは \(S_i\) (\(S_i > 0\)) である．

時刻 \(0\) に，区画 \(1\) から区画 \(N\) の方向に風が吹き始めた．隣り合う \(2\) つの区画について，時刻 \(t\) (\(0 \leqq t\)) において風上の区画の火が風下の区画の火より強いとき，時刻 \(t + 1\) における風下の区画の火の強さは，時刻 \(t\) における風上の区画の火の強さと同じになってしまう．そうでないときは，時刻 \(t + 1\) における風下の区画の火の強さは，時刻 \(t\) と同じである．すなわち，時刻 \(t\) (\(0 \leqq t\)) における区画 \(i\) (\(1 \leqq i \leqq N\)) の火の強さを \(S_i(t)\) と書くとすると，\(1 \leqq t\) ならば，\(S_i(t) = \max\{S_{i − 1}(t − 1), S_i(t − 1)\}\) となる．ただし，任意の \(t\) (\(0 \leqq t\)) に対して，\(S_0(t) = 0\) とし，任意の \(i\) (\(1 \leqq i \leqq N\)) に対し \(S_i(0) = S_i\) とする．

消防士であるあなたは \(Q\) 個の消火活動を計画した．\(Q\) 個の計画のうちどれか \(1\) つだけを実施する予定である．\(j\) 番目の計画 (\(1 \leqq j \leqq Q\)) は，時刻 \(T_j\) に，\(L_j \leqq k \leqq R_j\) となるすべての区画 \(k\) に消火剤を撒き，それらの区画を消火するというものである．火の強さが \(s\) である区画を消火するためには \(s\) リットルの消火剤が必要である．つまり，\(j\) 番目の計画の消火活動には \(S_{L_j}(T_j) + S_{L_j + 1}(T_j) + \cdots + S_{R_j}(T_j)\) リットルの消火剤が必要である．

どの計画を実行するか吟味するためにも，各計画に必要な消火剤の量が知りたい．

時刻 \(0\) における火の強さの情報と消火活動の計画の情報が与えられたとき，各計画に必要な消火剤の量を求めるプログラムを作成せよ．

Input

入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である．

\(N\) \(Q\)
\(S_1\) \(\cdots\) \(S_N\)
\(T_1\) \(L_1\) \(R_1\)
\(\vdots\)
\(T_Q\) \(L_Q\) \(R_Q\)

Output

標準出力に \(Q\) 行で出力せよ．第 \(j\) 行目 (\(1 \leqq j \leqq Q\)) には \(j\) 番目の計画に必要な消火剤の量を出力せよ．

Constraints

\(1 \leqq N \leqq 200\,000\)．
\(1 \leqq Q \leqq 200\,000\)．
\(1 \leqq S_i \leqq 1\,000\,000\,000\) (\(1 \leqq i \leqq N\))．
\(1 \leqq T_j \leqq N\) (\(1 \leqq j \leqq Q\))．
\(1 \leqq L_j \leqq R_j \leqq N\) (\(1 \leqq j \leqq Q\))．

Subtasks

(\(1\) 点) \(N \leqq 200\)，\(Q \leqq 200\)．
(\(6\) 点) \(T_1 = T_2 = \cdots = T_Q\)．
(\(7\) 点) \(L_j = R_j\) (\(1 \leqq j \leqq Q\))．
(\(6\) 点) \(S_i \leqq 2\) (\(1 \leqq i \leqq N\))．
(\(80\) 点) 追加の制約はない．

Examples

Sample input 1

Sample output 1

時刻 \(0\) における各区画の火の強さは，区画 \(1\) から順に \(9, 3, 2, 6, 5\) である．
時刻 \(1\) における各区画の火の強さは，区画 \(1\) から順に \(9, 9, 3, 6, 6\) である．よって，\(1\) 番目の計画に必要な消火剤の量は \(9 + 9 + 3 = 21\) リットルである．
時刻 \(2\) における各区画の火の強さは，区画 \(1\) から順に \(9, 9, 9, 6, 6\) である．よって，\(2\) 番目の計画に必要な消火剤の量は \(9 + 9 + 9 + 6 + 6 = 39\) リットルである．
時刻 \(3\) における各区画の火の強さは，区画 \(1\) から順に \(9, 9, 9, 9, 6\) である．よって，\(3\) 番目の計画に必要な消火剤の量は \(9 + 9 + 9 + 6 = 33\) リットルである．
時刻 \(4\) における各区画の火の強さは，区画 \(1\) から順に \(9, 9, 9, 9, 9\) である．よって，\(4\) 番目の計画に必要な消火剤の量は \(9\) リットルである．
時刻 \(5\) における各区画の火の強さは，区画 \(1\) から順に \(9, 9, 9, 9, 9\) である．よって，\(5\) 番目の計画に必要な消火剤の量は \(9 + 9 + 9 = 27\) リットルである．

入力例 \(1\) は小課題 \(1, 5\) の制約を満たす．

Sample input 2

10 10
3 1 4 1 5 9 2 6 5 3
1 1 6
2 8 10
4 2 7
8 3 3
6 1 10
3 2 8
5 1 9
7 4 5
9 7 9
10 10 10

Sample output 2

入力例 \(2\) は小課題 \(1, 5\) の制約を満たす．

Sample input 3

10 10
3 1 4 1 5 9 2 6 5 3
1 6 6
2 8 8
4 2 2
8 3 3
6 1 1
3 4 4
5 5 5
7 10 10
9 8 8
10 7 7

Sample output 3

入力例 \(3\) は小課題 \(1, 3, 5\) の制約を満たす．

Sample input 4

10 10
3 1 4 1 5 9 2 6 5 3
7 1 6
7 8 10
7 2 7
7 3 3
7 1 10
7 2 8
7 1 9
7 4 5
7 7 9
7 10 10

Sample output 4

入力例 \(4\) は小課題 \(1, 2, 5\) の制約を満たす．

Sample input 5

20 20
2 1 2 2 1 1 1 1 2 2 2 1 2 1 1 2 1 2 1 1
1 1 14
2 3 18
4 10 15
8 2 17
9 20 20
4 8 19
7 2 20
11 1 5
13 2 8
20 1 20
2 12 15
7 1 14
12 7 18
14 2 17
9 19 20
12 12 12
6 2 15
11 2 15
19 12 17
4 1 20

Sample output 5

入力例 \(5\) は小課題 \(1, 4, 5\) の制約を満たす．

Notes

JOI 2020 · JCIOI · CC BY-SA 4.0

Source

Olympiad › Japanese Olympiad in Informatics › JOI 2019-2020 Season › JOI 2020 Final Round5