#P13075. [NOISG 2019] Pilot

    ID: 12875 Type: RemoteJudge 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>2019NOISG(新加坡)

[NOISG 2019] Pilot

题目背景

小猫 Rar 终于实现了自己童年的梦想,成为了一名飞行员,想带他的朋友 Dinosaur 进行几次观光飞行。Rar 生活在一个线性的世界中,这个世界可以描述为一列 NN 个整数,第 ii 个整数 HiH_i 表示从世界最左端起第 ii 座山的高度。

题目描述

Rar 有 QQ 架飞机,第 ii 架飞机的最大巡航高度为 YiY_i 米。每次飞行从第 ss 座山起飞,到第 ee 座山降落,保证 ses \leq e,即 Rar 总是朝右飞行。

由于飞机有最大巡航高度,Rar 无法飞越、起飞或降落在高度大于巡航高度的山上。也就是说,若使用第 jj 架飞机,Rar 只能在满足 HiYjH_i \leq Y_j 的山上飞行。

对于第 ii 架飞机,请你帮助 Rar 计算,他一共可以进行多少次不同的飞行。也就是说,求有多少对 s,es,e 满足:

  • 1seN1 \leq s \leq e \leq N
  • ssee 之间所有山的高度均不超过该飞机的最大巡航高度。

输入格式

第一行包含两个整数 NNQQ

第二行包含 NN 个整数 H1,H2,,HNH_1, H_2, \dots, H_N

第三行包含 QQ 个整数 Y1,Y2,,YQY_1, Y_2, \dots, Y_Q

输出格式

输出 QQ 行,第 ii 行输出一个整数,表示使用第 ii 架飞机时,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:

对于第一架飞机,55 次飞行分别是:(1,1)(1,1)(3,3)(3,3)(5,5)(5,5)(5,6)(5,6)(6,6)(6,6)

对于第二架飞机,99 次飞行分别是:(1,1)(1,1)(1,2)(1,2)(1,3)(1,3)(2,2)(2,2)(2,3)(2,3)(3,3)(3,3)(5,5)(5,5)(5,6)(5,6)(6,6)(6,6)

对于第三架飞机,所有 2121 种飞行均可进行。

【数据范围】

  • 1N,Q,Hi,Yi1061 \leq N, Q, H_i, Y_i \leq 10^6
子任务编号 分值 额外限制
11 33 N=2, Q=1N = 2,\ Q = 1
22 1010 1N,Q301 \leq N, Q \leq 30
33 1212 1N,Q2001 \leq N, Q \leq 200
44 1515 1N,Q1031 \leq N, Q \leq 10^3
55 1N105, Q=1, Yi=1061 \leq N \leq 10^5,\ Q = 1,\ Y_i = 10^6
66 99 1N,Q105, Hi=i1 \leq N, Q \leq 10^5,\ H_i = i
77 1414 1N,Q105, H1 \leq N, Q \leq 10^5,\ H 严格递增
88 1010 1N105, Q=11 \leq N \leq 10^5,\ Q = 1
99 1111 1N,Q1051 \leq N, Q \leq 10^5
1010 无额外限制