← 返回题目列表

AtCoder · awc0096_e

E. 山脉远景

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

分数: 466 分

问题陈述

高桥是一位山地摄影师。有一条山脉自西向东呈直线延伸,由 N 山脉编号 1 to N 从西到东。山体海拔 i is H_i.

高桥正在计划 Q 照片拍摄。对于每一次拍摄 j,他的目标是距山的距离 L_j 去山 R_j,并从西侧(左侧)拍摄此间隔的照片。

从西侧看山脉时,一座山 k (L_j \le k \le R_j) 在区间内 [L_j, R_j] is 可见 如果在其西边的区间内没有山 严格更高 比山 k。正式来说,山 如果没有, k 可见 m 满意 L_j \le m < k 和 H_m > H_k。特别是最左边的山 间隔的 L_j 始终可见。

换句话说,如果您扫描区间内的海拔序列 [L_j, R_j] 从左到右,每次遇到海拔为 大于或等于 目前看到的最大海拔,最终统计的是可见山脉的数量。

对于每次拍摄的照片,确定可见山脉的数量。

约束

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j < R_j \leq N (1 \leq j \leq Q)
  • 所有输入值均为整数。

输入

N Q
H_1 H_2 \ldots H_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • 第一行包含一个整数 N 代表山脉的数量和一个整数 Q 代表查询数量,以空格分隔。
  • 第二行包含整数 H_1, H_2, \ldots, H_N 代表每座山的海拔,以空格分隔。
  • 以下 Q 行每行包含代表左端点的整数 L_j 和右端点 R_j 每张照片拍摄的间隔,以空格分隔。

输出

输出 Q 行。上 j第行,输出可见山脉的数量 j第一张照片拍摄。


示例输入 1

5 4
3 1 4 4 2
1 5
2 4
3 5
4 5

示例输出 1

3
3
2
1

示例输入 2

6 5
2 2 1 3 3 2
1 2
1 6
2 5
3 6
4 5

示例输出 2

2
4
3
3
2

示例输入 3

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

示例输出 3

7
3
5
5
4
5
3
3
3
2

示例输入 4

40 25
12 7 15 15 3 20 18 20 25 1 25 24 30 5 6 30 29 31 31 2 40 35 40 41 10 9 42 42 8 50 49 50 51 11 52 52 4 60 59 60
1 40
1 10
1 20
5 25
10 30
15 40
2 39
3 8
6 13
9 16
11 23
14 28
17 33
20 37
21 40
22 32
24 35
26 38
28 40
30 40
31 36
33 39
34 40
36 38
38 40

示例输出 4

23
6
11
12
12
16
22
4
5
4
7
10
11
11
12
7
7
9
8
7
5
4
5
2
2

示例输入 5

2 1
1000000000 1000000000
1 2

示例输出 5

2