4342. [国家集训队 2026]无题

【题目描述】

很久以前，小 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$ 场训练赛的方式中，所有训练赛的质量总和的最大值。

【样例输入】

2
4 3
3 2 4 1
3 1 4
5 5
10 3 16 8 7
1 2 3 4 5

【样例输出】

26 4 30
112 312 412 469 478

【数据规模与约定】

对于所有测试数据，均有：

- $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$。

【来源】

IOI2026中国国家集训队集中培训 Day3 Task1