A16511 | $Parallel Sums$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定两个整数 $n$ 和 $m$。对于一个长度为 $n$ 的整数序列 $A = (a_1, a_2, \ldots, a_n)$，它的平行和定义为 $n-m+1$ 个整数 $s_1, s_2, \ldots, s_{n-m+1}$，其中 $s_i = a_i + a_{i+1} + \ldots + a_{i+m-1}$，对于每个 $i$ 满足 $1 \leq i \leq n-m+1$。 现已给定 $s_1, s_2, \ldots, s_{n-m+1}$ 的具体值。你需要回答 $q$ 个询问，每个询问如下：对于第 $j$ 个询问，给定两个整数 $l_j$ 和 $r_j$，请你在所有符合条件的 $A=(a_1, a_2, \ldots, a_n)$（注意 $a_i$ 可以为负）中，找出区间 $a_{l_j}, a_{l_j+1}, \ldots, a_{r_j}$ 的最大值的最小可能取值。或者判断该最大值可以无限变小。

第一行输入两个整数 $n$ 和 $m$，满足 $1 \leq m \leq n \leq 200\,000$。 第二行输入 $n-m+1$ 个整数 $s_1, s_2, \ldots, s_{n-m+1}$，满足 $-10^9 \leq s_i \leq 10^9$。 第三行输入一个整数 $q$，满足 $1 \leq q \leq 100\,000$。 接下来的 $q$ 行，每行输入两个整数 $l_j$ 和 $r_j$，满足 $1 \leq l_j \leq r_j \leq n$。

输出 $q$ 行。第 $j$ 行输出第 $j$ 个询问的最小可能最大值。如果这个值可以无限变小，输出 unbounded。

输入 #1

输出 #1

2
unbounded
4
-1

C++ 编辑器

输入

输出