P14931 [北大集训 2025] 无题

很久以前，小 M 和他的朋友小 N 一起筹备了一场编程比赛。他们一共拟出了 $n$ 道题目，编号为 $1 \sim n$，其中第 $i$ ($1 \le i \le n$) 道题目的质量为非负整数 $a_i$。 时光飞逝。如今，小 M 不再是信息学奥林匹克竞赛的选手，但他们曾约定要一起举办一系列的比赛。 小 M 并没有忘记这件事。 现在，小 M 希望将这 $n$ 道题分成若干次训练赛，即将这 $n$ 道题划分为若干个连续区间。题目的划分方案可以用一列整数表示：$0 = r_0 < r_1 < r_2 < \cdots < r_k = n$，表示将会有 $k$ 次训练赛，第 $i$ 次训练赛将包含所有编号在 $(r_{i-1}+1)$ 到 $r_i$（两端都包含）的题目。 此外，小 M 希望给参赛选手提供尽可能好的比赛。小 M 观察到，一场比赛的质量是由其最好的题和最后一个题共同决定的。所以他规定：一场训练赛的质量为其所包含题目 $a_i$ 的最大值和所包含编号最大的题目的 $a_i$ 的乘积。 小 M 还没有决定比赛的场数，目前只有 $q$ 个候选值 $k_1, k_2, \ldots, k_q$。小 M 想知道，对于每个 $1 \le j \le q$，在所有的划分题目至恰好 $k_j$ 场训练赛的方式中，所有训练赛的质量总和最大是多少。

从标准输入读入数据。 本题包含多组测试数据。 输入的第一行包含一个正整数 $t$，表示测试数据组数。 接下来依次输入每组测试数据，对于每组测试数据： - 第一行包含两个正整数 $n, q$。 - 第二行包含 $n$ 个非负整数 $a_1, a_2, \ldots, a_n$。 - 第三行包含 $q$ 个正整数 $k_1, k_2, \ldots, k_q$。

输出到标准输出。 对于每组测试数据，输出一行 $q$ 个非负整数，其中第 $j$ ($1 \le j \le q$) 个非负整数表示在所有的划分题目至恰好 $k_j$ 场训练赛的方式中，所有训练赛的质量总和的最大值。

### 【子任务】 对于所有测试数据，均有： - $1 \le n, \sum n \le 5 \times 10^5$，$1 \le q, \sum q \le 10^5$； - 对于所有 $1 \le i \le n$，均有 $0 \le a_i \le 10^6$； - 对于所有 $1 \le j \le q$，均有 $1 \le k_j \le n$。 | 子任务编号 | 分值 | $\sum n \le$ | $\sum q \le$ | 特殊性质 | |:-:|:-:|:-:|:-:|:-:| | 1 | 10 | $300$ | $300$ | 无 | | 2 | 20 | $3000$ | $3000$ | 无 | | 3 | 10 | $10^5$ | $10$ | 无 | | 4 | 30 | $10^5$ | $10^5$ | 无 | | 5 | 10 | $5 \times 10^5$ | $10^5$ | $a_n = 0$ | | 6 | 20 | $5 \times 10^5$ | $10^5$ | 无 |