解题思路

目标：把序列划分成恰好 $m$ 个连续区间，最大化各区间最大值之和。
关键观察：每个区间贡献一个最大值。为了让这 $m$ 个最大值尽量大，最优策略是让这 $m$ 个区间分别“占有”序列中最大的 $m$ 个数（它们一定可以被分到 $m$ 个不同的连续段中）。
计算：将 $a$ 降序排序，取前 $m$ 个数求和即为答案。无需真正构造划分。

复杂度分析

时间复杂度： $O(n\log n)$ （每组数据）。需要对长度为 $n$ 的序列排序。所有测试的 $n$ 之和不超过 $2\times 10^5$ 。

给定长度为 $n$ 的序列 $a$ 。你需要把它划分成恰好 $m$ 个连续且首尾相接的区间 $[l_1,r_1],[l_2,r_2],\ldots,[l_m,r_m]$ ，满足对任意 $j$ （ $1 \le j < m$ ）都有 $r_j+1=l_{j+1}$ ，且覆盖整个序列。

记每个区间的峰值为该区间内元素的最大值。请最大化这 $m$ 个峰值之和。

本题有多组测试。数据组数 $T$ 满足 $1 \le T \le 100$ 。每组中 $1 \le m \le n \le 2 \times 10^5$ ，序列元素满足 $1 \le a_i \le 10^9$ 。同一测试文件中所有 $n$ 之和不超过 $2 \times 10^5$ 。