A6243. 「POI2010」积木 Blocks
编程题
提高+/省选-
知识点
题目描述
**译自 POI 2010 Stage 2. Day 1「[Blocks](https://szkopul.edu.pl/problemset/problem/4BL9eUWjrvT7ecMUJcmSuJI3/site/?key=statement)」**
给出 $n$ 个正整数 $a_1,a_2,\cdots a_n$ ，再给出一个正整数 $k$ ，现在可以进行如下操作：
* 每次选择一个大于 $k$ 的正整数 $a_i $，将 $a_i$ 减去 $1$ ，选择 $a_{i-1}$ 和 $a_{i+1}$ 中的一个加上 $1$ 。
经过一定次数的操作后，问最大能够选出多长的一个连续子序列，使得这个子序列的每个数都不小于 $k$ 。
总共给出 $m$ 次询问，每次询问给出的 $k$ 不同，你需要分别回答。
给出 $n$ 个正整数 $a_1,a_2,\cdots a_n$ ，再给出一个正整数 $k$ ，现在可以进行如下操作：
* 每次选择一个大于 $k$ 的正整数 $a_i $，将 $a_i$ 减去 $1$ ，选择 $a_{i-1}$ 和 $a_{i+1}$ 中的一个加上 $1$ 。
经过一定次数的操作后，问最大能够选出多长的一个连续子序列，使得这个子序列的每个数都不小于 $k$ 。
总共给出 $m$ 次询问，每次询问给出的 $k$ 不同，你需要分别回答。
输入格式
第一行两个空格隔开的正整数 $n,m$ 。
第二行 $n$ 个空格隔开的正整数 $a_1,a_2,\cdots a_n$ 。
第三行 $m$ 个空格隔开的正整数，表示每次询问的 $k$ 。
第二行 $n$ 个空格隔开的正整数 $a_1,a_2,\cdots a_n$ 。
第三行 $m$ 个空格隔开的正整数，表示每次询问的 $k$ 。
输出格式
一行， $m$ 个空格隔开的整数，第 $i$ 个数表示第 $i$ 次询问的 $k$ 对应的答案。
输入输出样例
输入 #1
5 6 1 2 1 1 5 1 2 3 4 5 6
输出 #1
5 5 2 1 1 0
说明/提示
对于 $100\%$ 的数据，有 $1\le n\le 1\ 000\ 000,1\le m\le 50,1\le a_i,k\le 10^9$。
Translated by vincent163
Translated by vincent163