

Time Limit: 5 sec / Memory Limit: 1024 MB
配点: 100 点
この問題は入力ファイルのサイズが大きく,低速な言語で満点を得るのは難しいので注意せよ.
問題
時は 22 世紀,新たに大手前高校の校長となったピ太郎の尽力により,大手前プロコンは世界中から注目されるイベントとなっていた.
大手前プロコン 21XX の開会式では,N 人の生徒が一列に並んで行進する.生徒が進む道は数直線としてあらわされる.生徒たちは全員,数直線上の正の方向を向いて行進する.時刻 0 に,前から i 番目 (1 \leq i \leq N) の生徒は,座標 −i に立っている.座標 0 には,旗手のピ太郎校長が立っている.
ピ太郎校長は,単位時刻あたり 1 だけ道の上を正の方向に進む.
すべての生徒には呑気さという値が定まっている.前から i 番目の生徒の呑気さは D_i である.各生徒は単位時間かけて同時に以下の行動を取る.
- 時刻 0 に前から i 番目にいた生徒は,時刻 0 に自分の目の前にいた参加者 (生徒またはピ太郎校長) との距離がちょうど D_i なら,距離 1 だけ 道の上を正の方向に進む.そうでないなら,動かない.
あなたは,開会式を見に来たきたむー教頭である.あなたは写真を撮らなければならなかったが,開会式の間中ずっと熟睡していた.仕方がないので,あなたは会場の写真を撮り,その写真に参加者の絵を描いて誤魔化すことにした.
誤魔化したことを明るみに出さないために,また絵を描く手間を見積もるために,あなたは以下の Q 個の値を知っておきたい.
- 時刻 T_j における,L_j 以上 R_j 以下の座標に立っている参加者の人数 (1 \leq j \leq Q)
各生徒の呑気さと,Q 個の質問の情報が与えられるので,それぞれの質問ごとに,条件を満たす参加者の人数を求めるプログラムを作成せよ.
制約
- 入力はすべて整数である.
- 1 \leq N \leq 500\,000.
- 1 \leq Q \leq 500\,000.
- 1 \leq D_i \leq 1\,000\,000\,000 (1 \leq i \leq N).
- 1 \leq T_j \leq 1\,000\,000\,000 (1 \leq j \leq Q).
- 1 \leq L_j \leq R_j \leq 1\,000\,000\,000 (1 \leq j \leq Q).
小課題
- (15 点) N, Q, D_i, T_j, L_j, R_j \leq 1\,000 (1 \leq i \leq N, 1 \leq j \leq Q).
- (16 点) T_i = T_j (1 \leq i,j \leq Q).
- (69 点) 追加の制約はない.
入力
入力は以下の形式で標準入力から与えられる.
N Q D_1 \vdots D_N T_1 L_1 R_1 \vdots T_Q L_Q R_Q
出力
標準出力に Q 行で出力せよ.j 行目 (1 \leq j \leq Q) には,j 個目の質問の答えを表す整数を出力せよ.
入力例 1
3 6 2 5 3 1 2 4 2 2 4 3 2 4 4 2 4 5 2 4 6 2 4
出力例 1
0 1 1 2 1 1
時刻 0 には,校長,選手 1,2,3 の順に,それぞれ座標 0,-1,-2,-3 にいる.
時刻 1 にはそれぞれ,座標 1,-1,-2,-3 にいる.
時刻 2 にはそれぞれ,座標 2,0,-2,-3 にいる.これは時刻 1 から時刻 2 にかけて,それぞれ次のような行動を取ったからである.
- 校長は場所 2 に移動する
- 選手 1 は前の参加者との差が 2 になったから場所 0 に移動する
- 選手 2 は前の参加者との差が 5 未満だから動かない
- 選手 3 は前の参加者との差が 3 未満だから動かない
時刻 3 にはそれぞれ,座標 3,1,-2,-3にいる.
入力例 2
4 2 1 1 1 1 2 1 4 1 3 6
出力例 2
2 0
入力例 3
6 6 11 36 28 80 98 66 36 29 33 190 171 210 18 20 100 1000 900 1100 92 87 99 200 100 300
出力例 3
0 2 0 4 1 4