← 返回题目列表

AtCoder · abc379_f

I. 建筑物 2

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

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