分数: 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