A182173.Yuilice 的展板取景
普及+/提高
官方
通过率:0%
时间限制:2.00s
内存限制:256MB
题目描述
Yuilice 把 n 张展板排成一行,从左到右编号为 1 到 n,第 i 张展板的亮度为正整数 ai。
她拍摄一次照片时,会选择一段连续的展板。照片必须包含至少一张、至多 k 张展板。
现在有 q 个彼此独立的取景要求。第 j 个要求给出一个亮度阈值 xj:照片中的每一张展板,亮度都必须大于或等于 xj。
对于每个要求,请计算有多少种合法的取景方案。选择的左端点或右端点不同,就视为不同方案。查询不会修改展板的亮度。
输入格式
第一行包含三个整数 n,k,q,分别表示展板数量、每张照片允许包含的最多展板数和取景要求的数量。
第二行包含 n 个正整数 a1,a2,…,an,其中 ai 表示第 i 张展板的亮度。
接下来 q 行,每行包含一个正整数 xj,表示第 j 个取景要求的亮度阈值。
输出格式
输出 q 行,第 j 行输出一个整数,表示满足第 j 个取景要求的方案数。不存在合法方案时输出 0。
输入输出样例
输入#1
5 2 4 2 5 4 4 1 1 4 5 6
输出#1
9 5 1 0
输入#2
1 1 2 1 1 2
输出#2
1 0
说明/提示
样例解释
样例 #1 中,阈值为 1 时,可以选择任意一张展板,或任意两张相邻展板,共 5+4=9 种方案。
阈值为 4 时,只有第 2 到第 4 张展板符合亮度要求。可以选择其中任意一张,或选择第 2,3 张、第 3,4 张,共 5 种方案。
阈值为 5 时只能选择第 2 张展板;阈值为 6 时没有方案。
样例 #2 中,唯一一张展板的亮度为 1,因此两个要求的答案依次为 1 和 0。
数据范围
对于所有测试数据,满足 1≤n,q≤2×105,1≤k≤n,1≤ai,xj≤109。
| 测试点编号 | n | q |
|---|---|---|
| 1∼4 | 1≤n≤200 | 1≤q≤200 |
| 5∼10 | 1≤n≤2000 | 1≤q≤2000 |
| 11∼20 | 1≤n≤2×105 | 1≤q≤2×105 |
输入解题思路,AI测评打分。不知道怎么写?