【MX-X4-T4】「Jason-1」一步最优

对于如下问题： - 给定长度为 $n$ 的数列 $a_1, \ldots, a_n$（其中 $a_i$ 可能为负数）以及一个正整数 $m$。 - 你需要选择不超过 $m$ 个数列 $a$ 的下标区间 $[l_j, r_j]$，且确保它们互不相交。 - 你需要最大化选择的区间中的元素之和的总和，即最大化 $\sum_j \sum_{i = l_j}^{r_j} a_i$。 考虑该贪心算法（并不正确）： - 重复如下过程 $m$ 次： - 在所有与当前已选择的区间不相交的区间（包括空区间）中，选择一个元素之和最大的区间。 - **如果有多个元素之和最大的区间，从中任意选择一个。** - 注：若选择了空区间，等价于中止过程，即选择的区间数量不超过 $m$ 个。 - 将如上过程中选择的所有非空区间中的元素之和作为答案。 现给定 $n$ 和数列 $a_1, \ldots, a_n$，对于每个 $m \in [1, n]$，请求出该算法可能得到的答案（即区间和的总和）的最大值和最小值。

**本题输入包含多组数据。** 第一行，一个正整数 $T$，表示数据组数。对于每组数据： - 第一行，一个正整数 $n$。 - 第二行，$n$ 个整数 $a_1, \ldots, a_n$。

对于每组数据： - 第一行，$n$ 个整数，第 $i$ 个整数表示当 $m = i$ 时，该算法能够得到的答案的**最大值**； - 第二行，$n$ 个整数，第 $i$ 个整数表示当 $m = i$ 时，该算法能够得到的答案的**最小值**。

5
5
1 -1 1 -1 1
5
2 -2 2 -1 2
6
3 1 -4 1 -5 9 
13
1 1 -4 5 -1 -4 1 9 1 9 -8 1 0
16
1 -8 2 -7 3 -6 4 -5 5 -4 4 -3 3 -2 2 -1

1 2 3 3 3
1 1 1 1 1
3 5 5 5 5
3 3 3 3 3
9 13 14 14 14 14
9 13 14 14 14 14
20 25 27 28 28 28 28 28 28 28 28 28 28
20 22 23 23 23 23 23 23 23 23 23 23 23
5 9 13 16 19 21 23 24 24 24 24 24 24 24 24 24
5 9 12 14 15 15 15 15 15 15 15 15 15 15 15 15

**【样例解释】** 对于第一组数据， - 一种取到最大值的方案为，依次选择区间 $[1,1],[3,3],[5,5],\varnothing, \varnothing$； - 一种取到最小值的方案为，依次选择区间 $[1,5],\varnothing,\varnothing,\varnothing,\varnothing$。 对于第二组数据， - 一种取到最大值的方案为，依次选择区间 $[3,5],[1,1],\varnothing,\varnothing,\varnothing$； - 一种取到最小值的方案为，依次选择区间 $[1,5],\varnothing,\varnothing,\varnothing,\varnothing$。 需要注意：在第一次更新时，无法选择区间 $[1,1],[1,3],[3,3]$ 等，因为它们不满足区间和在所有 $S$ 中的区间内最大（即 $= 3$）。在任意一次更新时，都无法选择区间 $[2,2]$，因为其区间和为 $-2$，而 $-2 < 0$（即空区间的区间和）。 对于第三组数据，只有唯一的选择方案，即依次选择区间 $[6,6],[1,2],[4,4],\varnothing,\varnothing,\varnothing$。 **【数据范围】** **本题采用捆绑测试。** | 子任务 | $n \le$ | $\sum n \le$ | 分值 | | :----------: | :----------: | :----------: | :----------: | | 1 | $10$ | $50$ | $17$ | | 2 | $100$ | $500$ | $24$ | | 3 | $2000$ | $10^4$ | $13$ | | 4 | $10^4$ | $5 \times 10^4$ | $9$ | | 5 | $10^5$ | $5 \times 10^5$ | $37$ | 对于 $100 \%$ 的数据，$1 \le T \le 10^4$，$1 \le n \le 10^5$，$\sum n \le 5 \times 10^{5}$，$|a_i| \le 10^9$。