配点: 100 点
输入文件较大且语言速度较慢时会出现此问题。满分获取难度较大,请小心。
問題
时间是 22 在就任大手前高中新任校长的 Pitaro 的努力下,大手前 Procon 成为了全世界瞩目的盛事。
Otemae Pro 控制器 在 21XX 开幕式上,N 学生们排成一排。学生所走的路径用数轴表示。所有学生都朝着数轴上的正方向行进。时间 0 之前 i 番目 (1 \leq i \leq N) 学生有坐标 站在 −i 。坐标 0 是旗手,Pitaro 校长。
校长 Pitaro 是 在道路上朝正方向前进 1 。
所有学生都有固定的开放程度。从正面看 i 学生的无忧无虑是 D_i 。每个学生在一个单位时间内同时执行以下操作。
- 時刻 0 之前 第 i 位学生是 0 与我面前的参与者(学生或Pitaro校长)的距离完全相同。 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