A182173.Yuilice 的展板取景

普及+/提高

官方

通过率:0%

时间限制:2.00s

内存限制:256MB

题目描述

Yuilice 把 nn 张展板排成一行,从左到右编号为 11 到 nn,第 ii 张展板的亮度为正整数 aia_i。

她拍摄一次照片时,会选择一段连续的展板。照片必须包含至少一张、至多 kk 张展板。

现在有 qq 个彼此独立的取景要求。第 jj 个要求给出一个亮度阈值 xjx_j:照片中的每一张展板,亮度都必须大于或等于 xjx_j。

对于每个要求,请计算有多少种合法的取景方案。选择的左端点或右端点不同,就视为不同方案。查询不会修改展板的亮度。

输入格式

第一行包含三个整数 n,k,qn,k,q,分别表示展板数量、每张照片允许包含的最多展板数和取景要求的数量。

第二行包含 nn 个正整数 a1,a2,…,ana_1,a_2,\ldots,a_n,其中 aia_i 表示第 ii 张展板的亮度。

接下来 qq 行,每行包含一个正整数 xjx_j,表示第 jj 个取景要求的亮度阈值。

输出格式

输出 qq 行,第 jj 行输出一个整数,表示满足第 jj 个取景要求的方案数。不存在合法方案时输出 00。

输入输出样例

  • 输入#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 中,阈值为 11 时,可以选择任意一张展板,或任意两张相邻展板,共 5+4=95+4=9 种方案。

阈值为 44 时,只有第 22 到第 44 张展板符合亮度要求。可以选择其中任意一张,或选择第 2,32,3 张、第 3,43,4 张,共 55 种方案。

阈值为 55 时只能选择第 22 张展板;阈值为 66 时没有方案。

样例 #2 中,唯一一张展板的亮度为 11,因此两个要求的答案依次为 11 和 00。

数据范围

对于所有测试数据,满足 1≤n,q≤2×1051\le n,q\le2\times10^5,1≤k≤n1\le k\le n,1≤ai,xj≤1091\le a_i,x_j\le10^9。

测试点编号 nn qq
1∼41\sim4 1≤n≤2001\le n\le200 1≤q≤2001\le q\le200
5∼105\sim10 1≤n≤20001\le n\le2000 1≤q≤20001\le q\le2000
11∼2011\sim20 1≤n≤2×1051\le n\le2\times10^5 1≤q≤2×1051\le q\le2\times10^5

输入解题思路,AI测评打分。不知道怎么写?

首页