题目背景
小猫 Rar 终于实现了自己童年的梦想,成为了一名飞行员,想带他的朋友 Dinosaur 进行几次观光飞行。Rar 生活在一个线性的世界中,这个世界可以描述为一列 N 个整数,第 i 个整数 Hi 表示从世界最左端起第 i 座山的高度。
题目描述
Rar 有 Q 架飞机,第 i 架飞机的最大巡航高度为 Yi 米。每次飞行从第 s 座山起飞,到第 e 座山降落,保证 s≤e,即 Rar 总是朝右飞行。
由于飞机有最大巡航高度,Rar 无法飞越、起飞或降落在高度大于巡航高度的山上。也就是说,若使用第 j 架飞机,Rar 只能在满足 Hi≤Yj 的山上飞行。
对于第 i 架飞机,请你帮助 Rar 计算,他一共可以进行多少次不同的飞行。也就是说,求有多少对 s,e 满足:
- 1≤s≤e≤N;
- s 到 e 之间所有山的高度均不超过该飞机的最大巡航高度。
输入格式
第一行包含两个整数 N 和 Q。
第二行包含 N 个整数 H1,H2,…,HN。
第三行包含 Q 个整数 Y1,Y2,…,YQ。
输出格式
输出 Q 行,第 i 行输出一个整数,表示使用第 i 架飞机时,Rar 可以进行的不同飞行次数。
6 3
1 3 2 4 1 2
2 3 4
5
9
21
6 3
2 2 5 2 2 2
1 2 10
0
9
21
2 1
1 2
1000000
3
提示
【样例解释】
对于样例 1:
对于第一架飞机,5 次飞行分别是:(1,1)、(3,3)、(5,5)、(5,6)、(6,6)。
对于第二架飞机,9 次飞行分别是:(1,1)、(1,2)、(1,3)、(2,2)、(2,3)、(3,3)、(5,5)、(5,6)、(6,6)。
对于第三架飞机,所有 21 种飞行均可进行。
【数据范围】
- 1≤N,Q,Hi,Yi≤106
子任务编号 |
分值 |
额外限制 |
1 |
3 |
N=2, Q=1 |
2 |
10 |
1≤N,Q≤30 |
3 |
12 |
1≤N,Q≤200 |
4 |
15 |
1≤N,Q≤103 |
5 |
1≤N≤105, Q=1, Yi=106 |
6 |
9 |
1≤N,Q≤105, Hi=i |
7 |
14 |
1≤N,Q≤105, H 严格递增 |
8 |
10 |
1≤N≤105, Q=1 |
9 |
11 |
1≤N,Q≤105 |
10 |
无额外限制 |