/
Time Limit: 2 sec / Memory Limit: 256 MiB
Score: 100 points
Problem Statement
At the opening ceremony of IOI 2018, N contestants marches along a line, which is represented by a number line. All contestants head for the positive direction of the number line. At time 0, the i-th contestant (1 \le i \le N, counted from the front) stands at coordinate -i. In addition, IOI-chan, the flag-bearer, stands at coordinate 0.
Each contestant has a value called slowness. The i-th contestant has slowness D_{i}. The contestants keep the following rule:
- If the i-th contestant is at a distance greater than or equal to D_{i} + 1 from the person (a contestant or IOI-chan) right in front of him or her, the i-th contestant moves to the position at a distance 1 from that person. Otherwise, the i-th contestant does not move.
IOI-chan moves a distance 1 in the positive direction on the line per unit time. A contestant moves instantly whenever the condition described above is satisfied.
You are a reporter to cover the opening ceremony. You had to take photos, but you were fast asleep during the whole ceremony. It couldn’t be helped—you decided to cheat by taking photos of the hall and then drawing pictures of the people on them.
In order not to get caught cheating, or to estimate the time to draw pictures, you want to know the following Q values:
- the number of people standing at coordinate between L_{j} and R_{j}, inclusive, at time T_{j} (1 \le j \le Q).
Task
Given the slowness of each contestant and the data of the Q questions, write a program which calculates the number of people satisfying the condition for each question.
Input
Read the following data from the standard input.
- The first line of the input contains two space separated integers N and Q. This means there are N contestants (not including IOI-chan) and there are Q questions.
- The i-th line (1 \le i \le N) of the following N lines contains an integer D_{i}. This means the i-th contestant from the front has slowness D_{i}.
- The j-th line (1 \le j \le Q) of the following Q lines contains three space separated integers T_{j}, L_{j} and R_{j}. These values represent the j-th question.
Output
Write Q lines to the standard output. The j-th line (1 \le j \le Q) of the output should contain the answer to the j-th question.
Constraints
All input data satisfy the following conditions.
- 1 \le N \le 500\,000.
- 1 \le Q \le 500\,000.
- 1 \le D_{i} \le 1\,000\,000\,000 (1 \le i \le N).
- 1 \le T_{j} \le 1\,000\,000\,000 (1 \le j \le Q).
- 1 \le L_{j} \le R_{j} \le 1\,000\,000\,000 (1 \le j \le Q).
Subtasks
There are 3 subtasks. The score and additional constraints of each subtask are as follows:
Subtask 1 [7 points]
- D_{i} = 1 (1 \le i \le N).
Subtask 2 [12 points]
- N \le 1\,000.
- Q \le 1\,000.
- T_{j} \le 1\,000 (1 \le j \le Q).
- 1 \le L_{j} \le R_{j} \le 1\,000 (1 \le j \le Q).
Subtask 3 [81 points]
There are no additional constraints.
Sample Input and Output
Sample Input 1
3 6 2 5 3 1 2 4 2 2 4 3 2 4 4 2 4 5 2 4 6 2 4
Sample Output 1
0 1 1 2 1 2
In this sample input, the contestants and IOI-chan move as follows.
In the following, interval [L, R] denotes the set of points of coordinate between L and R, inclusive, on the number line.
- At time 0, IOI-chan stands at coordinate 0. The 1st, 2nd and 3rd contestants stand at coordinates -1, -2 and -3, respectively.
- At time 1, IOI-chan moves to coordinate 1. No contestants move; the 1st, 2nd and 3rd contestants stand at coordinates -1, -2 and -3, respectively. Since there are no people in interval [2, 4], output 0 for the 1st question.
- At time 2, IOI-chan moves to coordinate 2. The distance between IOI-chan and the 1st contestant is now 3, so the 1st contestant moves to coordinate 1. The 1st, 2nd and 3rd contestants stand at coordinates 1, -2 and -3, respectively. Since there is only IOI-chan in interval [2, 4], output 1 for the 2nd question.
- At time 3, IOI-chan moves to coordinate 3. No contestants move; the 1st, 2nd and 3rd contestants stand at coordinates 1, -2 and -3, respectively. Since there is only IOI-chan in interval [2, 4], output 1 for the 3rd question.
- At time 4, IOI-chan moves to coordinate 4. The distance between IOI-chan and the 1st contestant is now 3, so the 1st contestant moves to coordinate 3. The 1st, 2nd and 3rd contestants stand at coordinates 3, -2 and -3, respectively. Since there are IOI-chan and the 1st contestant in interval [2, 4], output 2 for the 4th question.
- At time 5, IOI-chan moves to coordinate 5. No contestants move; the 1st, 2nd and 3rd contestants stand at coordinates 3, -2 and -3, respectively. Since there is only the 1st contestant in interval [2, 4], output 1 for the 5th question.
- At time 6, IOI-chan moves to coordinate 6. The distance between IOI-chan and the 1st contestant is now 3, so the 1st contestant moves to coordinate 5. Then, the distance between the 1st and 2nd contestants is now 7, so the 2nd contestant moves to coordinate 4. Furthermore, the distance between the 2st and 3nd contestants is now 7, so the 3nd contestant moves to coordinate 3. The 1st, 2nd and 3rd contestants stand at coordinate 5, 4 and 3, respectively. Since there are the 2nd and 3rd contestants in interval [2, 4], output 2 for the 6th question.
Sample Input 2
4 2 1 1 1 1 2 1 4 1 3 6
Sample Output 2
2 0
This sample input satisfies the constraints for subtask 1.
Sample Input 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
Sample Output 3
1 6 0 5 2 7
配点 : 100 点
問題文
IOI 2018 の開会式では,N 人の選手が一列に並んで行進する.選手が進む道は数直線としてあらわされる.選手たちは全員,数直線上の正の方向を向いて行進する.最初,前から i 番目 (1 \leqq i \leqq N) の選手は,座標 -i に立っている.座標 0 には,旗手の IOI ちゃんが立っている.
すべての選手には呑気さという値が定まっている.前から i 番目の選手の呑気さは D_{i} である.選手たちは,常に,以下の規則で行動する.
- 前から i 番目の選手は,自分の目の前の参加者 (選手または IOI ちゃん) との距離が D_{i} + 1 以上離れたなら,目の前の参加者から距離 1 の位置まで進む.そうでないなら,動かない.
IOI ちゃんは,単位時刻あたり 1 だけ道の上を正の方向に進む.選手たちは全員,上記の条件が満たされれば即座に進む.
あなたは,開会式を取材しに来た記者である.あなたは写真を撮らなければならなかったが,開会式の間中ずっと熟睡していた.仕方がないので,あなたは会場の写真を撮り,その写真に参加者の絵を描いて誤魔化すことにした.
誤魔化したことを明るみに出さないために,また絵を描く手間を見積もるために,あなたは以下の Q 個の値を知っておきたい.
- 時刻 T_{j} における,L_{j} 以上 R_{j} 以下の座標に立っている参加者の人数 (1 \leqq j \leqq Q)
課題
各選手の呑気さと,Q 個の質問の情報が与えられるので,それぞれの質問ごとに,条件を満たす参加者の人数を求めるプログラムを作成せよ.
入力
標準入力から以下の入力を読み込め.
- 1 行目には,整数 N, Q が空白を区切りとして書かれている.これらは順に,選手の人数と,質問の個数を表す.選手の人数に IOI ちゃんは含まれないことに注意せよ.
- 続く N 行のうちの i 行目 (1 \leqq i \leqq N) には,整数 D_{i} が書かれている.これらは順に,前から i 番目の選手の呑気さを表す.
- 続く Q 行のうちの j 行目 (1 \leqq j \leqq Q) には,整数 T_{j}, L_{j}, R_{j} が空白を区切りとして書かれている.これらは j 個目の質問の情報を表す.
出力
標準出力に Q 行で出力せよ .j 行目 (1 \leqq j \leqq Q) には,j 個目の質問の答えを表す整数を出力せよ.
制限
すべての入力データは以下の条件を満たす.
- 1 \leqq N \leqq 500\,000.
- 1 \leqq Q \leqq 500\,000.
- 1 \leqq D_{i} \leqq 1\,000\,000\,000 (1 \leqq i \leqq N).
- 1 \leqq T_{j} \leqq 1\,000\,000\,000 (1 \leqq j \leqq Q).
- 1 \leqq L_{j} \leqq R_{j} \leqq 1\,000\,000\,000 (1 \leqq j \leqq Q).
小課題
小課題 1 [7 点]
- D_{i} = 1 (1 \leqq i \leqq N).
小課題 2 [12 点]
以下の条件を満たす.
- N \leqq 1\,000.
- Q \leqq 1\,000.
- T_{j} \leqq 1\,000 (1 \leqq j \leqq Q).
- 1 \leqq L_{j} \leqq R_{j} \leqq 1\,000 (1 \leqq j \leqq Q).
小課題 3 [81 点]
追加の制限はない.
入出力例
入力例 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 2
この入力例では,選手と IOI ちゃんは以下のように進む.
以下では,数直線上において,座標が L 以上 R 以下の点の全体を区間 [L, R] で表す.
- 最初,IOI ちゃんは座標 0 に,1, 2, 3 番目の選手は座標 -1, -2, -3 にいる.
- 時刻 1 に,IOI ちゃんは座標 1 に進む.進む選手はおらず,1, 2, 3 番目の選手は座標 -1, -2, -3 にいる.区間 [2, 4] には誰もいないので,1 個目の質問には 0 を出力する.
- 時刻 2 に,IOI ちゃんは座標 2 に進む.IOI ちゃんと 1 番目の選手の間の距離が 3 になったため,1 番目の選手は座標 1 に進む .1, 2, 3 番目の選手は座標 1, -2, -3 にいる.区間 [2, 4] には IOI ちゃんのみがいるので,2 個目の質問には 1 を出力する.
- 時刻 3 に,IOI ちゃんは座標 3 に進む.進む選手はおらず,1, 2, 3 番目の選手は座標 1, -2, -3 にいる.区間 [2, 4] には IOI ちゃんのみがいるので,3 個目の質問には 1 を出力する.
- 時刻 4 に,IOI ちゃんは座標 4 に進む.IOI ちゃんと 1 番目の選手の間の距離が 3 になったため,1 番目の選手は座標 3 に進む .1, 2, 3 番目の選手は座標 3, -2, -3 にいる.区間 [2, 4] には IOI ちゃんと 1 番目の選手がいるので,4 個目の質問には 2 を出力する.
- 時刻 5 に,IOI ちゃんは座標 5 に進む.進む選手はおらず,1, 2, 3 番目の選手は座標 3, -2, -3 にいる.区間 [2, 4] には 1 番目の選手のみがいるので,5 個目の質問には 1 を出力する.
- 時刻 6 に,IOI ちゃんは座標 6 に進む.IOI ちゃんと 1 番目の選手の間の距離が 3 になったため,1 番目の選手は座標 5 に進む.さらに,1 番目の選手と 2 番目の選手の間の距離が 7 になったため,2 番目の選手は座標 4 に進む.さらに,2 番目の選手と 3 番目の選手の間の距離が 7 になったため,3 番目の選手は座標 3 に進む .1, 2, 3 番目の選手は座標 5, 4, 3 にいる.区間 [2, 4] には 2 番目の選手と 3 番目の選手がいるので,6 個目の質問には 2 を出力する.
入力例 2
4 2 1 1 1 1 2 1 4 1 3 6
出力例 2
2 0
この入力例は,小課題 1 の条件を満たす.
入力例 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
1 6 0 5 2 7