← 返回题目列表

AtCoder · otemae2019_e

E. 最差班主任

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

配点: 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).

小課題

  1. (15 点) N, Q, D_i, T_j, L_j, R_j \leq 1\,000 (1 \leq i \leq N, 1 \leq j \leq Q).
  2. (16 点) T_i = T_j (1 \leq i,j \leq Q).
  3. (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