#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, k, a[300005];
set<pair<int, int>, greater<pair<int, int>>> trs;
set<pair<int, int>> poses;

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		if (i != 1) {
			trs.insert({a[i - 1] - a[i], i - 1});
			poses.insert({i - 1, a[i - 1] - a[i]});
		}
	}
	int sum = 0;
	for (int i = 1; i <= k; ++i) {
		assert(trs.size());
		pair<int, int> val = *(trs.begin()); trs.erase(trs.begin());
		sum += val.first;
		assert(poses.find({val.second, val.first}) != poses.end());
		poses.erase({val.second, val.first});
		int newval = -val.first;
		{
			auto it = poses.upper_bound({val.second, -(1ll<<60)});
			if (it != poses.end()) {
				newval += it -> second;
				assert(trs.find({it -> second, it -> first}) != trs.end());
				trs.erase({it -> second, it -> first});
				poses.erase(it);
			}
		}
		{
			auto it = poses.lower_bound({val.second, -(1ll<<60)});
			if (it != poses.begin()) {
				--it;
				newval += it -> second;
				assert(trs.find({it -> second, it -> first}) != trs.end());
				trs.erase({it -> second, it -> first});
				poses.erase(it);
			}
		}
		trs.insert({newval, val.second});
		poses.insert({val.second, newval});
	}
	cout << -sum << "\n";
}

思路：

• 一定不会有相交的情况，所以就一定是差分之后转换为 P1484。
• 然后直接转过来就是了。

可是我发现我输出的比答案小，到底是转换有问题还是 P1484 数据太水了。