P13523 [KOI 2025 #2] 序列与查询

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。 **本题测试数据极大，评测时可能需要 2-3 分钟时间预加载数据。**

对于一个长度为 $l$ 的序列 $[B_1, B_2, \ldots, B_l]$，序列的**连续子区间**被定义为像 $[B_i, B_{i+1}, \ldots, B_j]$ 这样在序列中连续出现的数的子序列。连续子区间不能为空。即，必须满足 $1 \le i \le j \le l$。 对于一个长度为 $l$ 的序列 $[B_1, B_2, \ldots, B_l]$，序列的**最大连续子区间和**被定义为该序列所有连续子区间的元素和中的最大值。例如，序列 $[6, -7, 3, -1, 5, 2]$ 的最大连续子区间和是 9，这可以通过选取子区间 $[3, -1, 5, 2]$ 得到。如果用数学符号表示序列 $B$ 的最大连续子区间和，则为 $\max_{1 \le i \le j \le l}(\sum_{k=i}^{j} B_k)$。 给定一个长度为 $N$ 的序列 $[A_1, A_2, \ldots, A_N]$ 和 $Q$ 个查询。第 $i$ 个查询由一个整数 $X_i$ 表示。当给定 $X_i$ 时，你需要计算序列 $[A_1 + X_i, A_2 + X_i, \ldots, A_N + X_i]$ 的最大连续子区间和。

第一行给定 $N, Q$，以空格分隔。 第二行给定 $A_1, A_2, \ldots, A_N$，以空格分隔。 第三行给定 $X_1, X_2, \ldots, X_Q$，以空格分隔。

输出 $Q$ 行。其中第 $i(1 \le i \le Q)$ 行输出序列 $[A_1 + X_i, A_2 + X_i, \ldots, A_N + X_i]$ 的最大连续子区间和。

### 限制条件 * 所有给定的数都是整数。 * $1 \le N \le 1\,000\,000$ * $1 \le Q \le 1\,000\,000$ * 对于所有满足 $1 \le i \le N$ 的 $i$，有 $-10^9 \le A_i \le 10^9$。 * 对于所有满足 $1 \le i \le Q$ 的 $i$，有 $-10^9 \le X_i \le 10^9$。 ### 子任务 1. (5 分) $N, Q \le 300$ 2. (5 分) $N \le 300$ 3. (28 分) $N \le 10\,000$ 4. (17 分) $N \le 125\,000$ 5. (16 分) $N \le 250\,000$ 6. (15 分) $N \le 500\,000$ 7. (14 分) 无额外限制条件。