← 返回题目列表

AtCoder · awc0041_e

E. 建筑景观

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

分数: 466 分

问题陈述

高桥是一名城市规划测量师。沿着笔直的街道, N 建筑物鳞次栉比。它们的编号为“大楼” 1,建筑 2, ..., 建筑 N 从左到右,以及建筑物的高度 i is H_i。所有建筑物的高度都是不同的。

对于每栋建筑 i (1 \leq i \leq N),我们定义一个 “查看分数” 如下。

首先,大楼右侧的建筑物中 i (数字大于 i) 比建筑物高 i,让建筑 R_i 是最近的一个。也就是说, R_i 是最小的 j > i 这样 H_j > H_i。如果不存在这样的建筑物,那么 R_i 不存在。

同样,在大楼左侧的建筑物中 i (数字小于 i) 比建筑物高 i,让建筑 L_i 是最近的一个。也就是说, L_i 是最大的 j < i 这样 H_j > H_i。如果不存在这样的建筑物,那么 L_i 不存在。

直观上看,Building的视图得分 i 是包含 Building 的连续区间内的建筑物数量 i 向左和向右延伸,直到在每个方向上到达更高的建筑物(或街道的尽头)。具体确定如下:

  • 如果两者 L_i 和 R_i 存在:分数为 R_i - L_i - 1 (建筑物之间的建筑物数量 L_i 和建筑 R_i)
  • 如果只有 R_i 存在并且 L_i 不存在:分数为 R_i - 1 (来自 Building 的建筑物数量 1 前往大楼 R_i - 1)
  • 如果只有 L_i 存在并且 R_i 不存在:分数为 N - L_i (来自 Building 的建筑物数量 L_i + 1 前往大楼 N)
  • 如果两者都不存在:分数为 N (建筑物总数)

高桥需要回答 Q 问题。对于每个问题,一个整数 给出了 X_k 。回答 景观得分至少为的建筑物数量 X_k.

约束

  • 1 \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)
  • 全部 H_i 是不同的
  • 1 \leq X_k \leq N (1 \leq k \leq Q)
  • 所有输入值均为整数

输入

N Q
H_1 H_2 \cdots H_N
X_1
X_2
\vdots
X_Q
  • 第一行包含两个用空格分隔的整数: N,建筑物数量,以及 Q,问题数量。
  • 第二行包含 N 整数 H_1, H_2, \ldots, H_N 由空格分隔,代表建筑物的高度。全部 H_i 是不同的。
  • 以下 Q 行每行包含一个整数 X_k,代表每个问题的值。

输出

输出 Q 行。上 k- 第行 (1 \leq k \leq Q),输出答案 k第题,即视野得分至少为的建筑物数量 X_k.


示例输入 1

5 4
3 1 4 2 5
1
2
3
5

示例输出 1

5
3
2
1

示例输入 2

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

示例输出 2

7
3
2
1

示例输入 3

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

示例输出 3

10
6
4
2
1

示例输入 4

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

示例输出 4

15
8
4
1
1
1

示例输入 5

1 1
1000000000
1

示例输出 5

1