A5390 | $台阶前缀查询$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

有一段台阶，共有 $n$ 级，第 $i$ 级台阶的高度为 $a_i$。 接下来有 $q$ 次询问。每次给出一个数 $k$，你需要： 从第 $1$ 级台阶开始往上走，只要遇到的最高台阶高度不超过 $k$，就一直走； 设能走到的最远位置为第 $i$ 级（若第 $1$ 级的高度就大于 $k$，则 $i=0$），请输出从第 $1$ 级到第 $i$ 级所有台阶高度之和：$\sum_{j=1}^{i} a_j$。 等价地说：令前缀最大值数组 $p_i=\max(a_1,\dots,a_i)$，前缀和 $s_i=\sum_{j=1}^{i} a_j$。 对每个询问的 $k$，找到最大的 $i$ 使得 $p_i\le k$，答案为 $s_i$（若不存在则输出 $0$）。

第一行两个整数 $n, q$ —— 台阶数与询问数。 第二行 $n$ 个整数 $a_1,\dots,a_n$。 第三行 $q$ 个整数 $k_1,\dots,k_q$，分别为每个询问给出的 $k$。

输出一行包含 $q$ 个整数，第 $i$ 个数是对 $k_i$ 的答案。数之间用空格分隔。

输入 #1

4 5
1 2 1 5
1 2 4 9 10

输出 #1

1 4 4 9 9

C++ 编辑器

输入

输出