分数: 550 点
问题陈述
有 N 建筑物,建筑物 1, 建筑 2, \ldots, 建筑 N,从西向东按此顺序直线排列。建筑 1 是最西边的建筑物 N 是最东端。建筑物高度 i\ (1\leq i\leq N) is H_i.
对于一对整数 (i,j)\ (1\leq i\lt j\leq N), 建筑 j 从建筑物中可以看到 i 如果满足以下条件。
- 没有比建筑物更高的建筑物 j 建筑物之间 i 和 j。换句话说,不存在整数 k\ (i\lt k\lt j) 这样 H_k > H_j.
你被给予 Q 查询。在 i-第一个查询,给定一对整数 (l_i,r_i)\ (l_i\lt r_i),查找建筑物以东的建筑物数量 r_i (即建筑物 r_i + 1, r_i + 2, \ldots, N)从两座建筑物都可以看到 l_i 和 r_i.
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq H_i \leq N
- H_i\neq H_j\ (i\neq j)
- 1 \leq l_i < r_i \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q H_1 H_2 \ldots H_N l_1 r_1 l_2 r_2 \vdots l_Q r_Q
输出
打印 Q 行。的 i- 第行 (1 \leq i \leq Q)应包含以下问题的答案 i第一个查询。
示例输入 1
5 3 2 1 4 3 5 1 2 3 5 1 4
示例输出 1
2 0 1
- 第一个查询,在建筑物东边的建筑物中 2, 建筑物 从两座建筑物都可以看到 3 和 5 从两座建筑都可以看到 1 和 2,所以答案是 2.
- 对于第二个查询,建筑物东边没有建筑物 5.
- 对于第三个查询,在建筑物以东的建筑物中 4, 建筑 5 从两座建筑都可以看到 1 和 4,所以答案是 1.
示例输入 2
10 10 2 1 5 3 4 6 9 8 7 10 3 9 2 5 4 8 5 6 3 8 2 10 7 8 6 7 8 10 4 10
示例输出 2
1 3 1 2 1 0 1 1 0 0