CF2206E Parallel Sums

给定两个整数 $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 解析： 对于第一个询问，可以取 $A = (9, -4, -3, 2, 1, 2, 1, 1)$，平行和为 $(4, -4, 2, 6, 5)$，满足要求。此时 $\max(a_3, \ldots, a_7) = \max(-3, 2, 1, 2, 1) = 2$，且可以证明 2 是最小可能值。 对于第二个询问，可以让该值任意小。 对于第三个询问，可以取 $A = (4, -3, 0, 3, -4, 3, 4, 2)$，此时整个序列的最大值是 4，这是最小可能值。 由 ChatGPT 5 翻译