P11064 [MX-X4-T4] "Jason-1" One-Step Optimal

Original link: 。

For the following problem: - You are given an array $a_1, \ldots, a_n$ of length $n$ (where $a_i$ may be negative) and a positive integer $m$. - You need to choose at most $m$ index intervals $[l_j, r_j]$ of array $a$, and ensure that they are pairwise disjoint. - You need to maximize the total sum of the elements inside the chosen intervals, i.e., maximize $\sum_j \sum_{i = l_j}^{r_j} a_i$. Consider the following greedy algorithm (which is incorrect): - Repeat the following process $m$ times: - Among all intervals that do not intersect any currently chosen interval (including the empty interval), choose an interval with the maximum element sum. - **If there are multiple intervals with the maximum element sum, choose any one of them.** - Note: If the empty interval is chosen, it is equivalent to stopping the process, i.e., the number of chosen intervals is less than or equal to $m$. - Take the sum of the elements in all non-empty intervals chosen in the process above as the answer. Now you are given $n$ and the array $a_1, \ldots, a_n$. For each $m \in [1, n]$, find the maximum possible value and the minimum possible value of the answer (i.e., the total of interval sums) that this algorithm may produce.

**This problem contains multiple test cases.** The first line contains a positive integer $T$, the number of test cases. For each test case: - The first line contains a positive integer $n$. - The second line contains $n$ integers $a_1, \ldots, a_n$.

For each test case: - The first line contains $n$ integers. The $i$-th integer denotes the **maximum value** of the answer that the algorithm can obtain when $m = i$. - The second line contains $n$ integers. The $i$-th integer denotes the **minimum value** of the answer that the algorithm can obtain when $m = i$.

**Sample Explanation** For the first test case: - One way to achieve the maximum is to select intervals $[1,1],[3,3],[5,5],\varnothing,\varnothing$ in order. - One way to achieve the minimum is to select intervals $[1,5],\varnothing,\varnothing,\varnothing,\varnothing$ in order. For the second test case: - One way to achieve the maximum is to select intervals $[3,5],[1,1],\varnothing,\varnothing,\varnothing$ in order. - One way to achieve the minimum is to select intervals $[1,5],\varnothing,\varnothing,\varnothing,\varnothing$ in order. Note: In the first update, you cannot choose intervals like $[1,1],[1,3],[3,3]$, because they do not satisfy that their interval sum is the maximum among all intervals in $S$ (i.e., $= 3$). In any update, you can never choose interval $[2,2]$, because its interval sum is $-2$, and $-2 < 0$ (which is the interval sum of the empty interval). For the third test case, there is only one possible selection scheme, i.e., select intervals $[6,6],[1,2],[4,4],\varnothing,\varnothing,\varnothing$ in order. **Constraints** **This problem uses bundled testdata.** | Subtask | $n \le$ | $\sum n \le$ | Score | | :----------: | :----------: | :----------: | :----------: | | 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$ | For $100\%$ of the testdata, $1 \le T \le 10^4$, $1 \le n \le 10^5$, $\sum n \le 5 \times 10^{5}$, and $|a_i| \le 10^9$。 Translated by ChatGPT 5