題意

U2FsdGVkX1+8uiG+PpDgKVLkStC7xLTSgybYosNzawTaA6uCLLvVEEuPxRrxWlT6
OqVxsKco36vWm0b7q6zTMswe8U/k4EKQ1JrjX8srH5AUH2JLR2lte2t8oT6ygpVX
iOefX4EweVO4+1FSuALHNNiTIV5LNSeISXfyA0B4HdDTm3/g9IVcx7FhwjjvcNEh
RdqojfMfNcYTLHsDFTLQlkI75hlDXSuR+0uuq6TDvw+BTWrlRAVqkBijrOU4X9Ja
bBtRpQqPK5Q8lorSfZTDaPoL2kn5FNoN1+aZaeGXnp4=

解析

分成兩種情況，分出來的集合存在某個集合交為空，和不存在任何一個集合交為空。

若分出來的集合存在某個交為空，那麼空集一定最多有一個，因為多個空集可以合併成一個空集。可以得到最優的方案一定是長度前 k-1 大的分別單獨分一個集合，然後其他線段分成一個集合。

然後不存在某個集合交為空。

假設存線上段 [l1, r1] 和 [l2, r2]，使得 l1 <= l2 <= r2 <= l2，考慮 [l1, r1] 放在哪個集合。如果 [l1, r1] 不和 [l2, r2] 在一個集合，且不單獨佔一個集合，那麼可以把 [l1, r1] 放到 [l2, r2] 同一個集合，這樣答案不會更劣，而這時 [l1, r1] 實際上沒有起什麼影響，可以忽略。所以如果存在某個線段包含其他線段，我們可以直接忽略這個包含其他線段的線段，最後再列舉有多少個這種包含線段獨佔集合。

除去所有包含線段後，可以排序使得所有其他線段 l 和 r 都單調遞增。可以證明，最優解一定可以調整成只有每個集合都的線段都是連續的。

A: |----------|
B:   |-------------|
C:     |----------------|
D:         |---------------|
E:          |---------------|

假設當前最優解中，ABDE 在一個集合，C 和 A 前面的某個線段在一個集合，那麼你調整成 CDE 一個集合，AB 和前面的一個集合一定不劣。

令第 i 集合最靠前的線段為 sis_{i}，那麼長度可以寫成：

rs0−ls1−1+rs1−ls2−1+rs2−ls3−1+⋯+rsk−1−lnr_{s_{0}} - l_{s_{1} - 1} + r_{s_{1}} - l_{s_{2} - 1} + r_{s_{2}} - l_{s{3} - 1} + \cdots + r_{s_{k-1}} - l_{n}

可以把每個位置 i 的 ri−li−1r_{i} - l_{i-1} 排序，然後貪心取出前 k 大，再和前面包含線段組合一下即可。

時間複雜度 O(nlog⁡n)O(n\log n)。

實現

struct seg_t
{
	int l, r;
	seg_t() = default;
	seg_t(int l, int r) : l(l), r(r) {}
	int len() const { return r - l; }
};

long long solve1(int k, std::vector<seg_t> segs)
{
	int n = segs.size();
	std::sort(segs.begin(), segs.end(), [](const seg_t &a, const seg_t &b)
		  {
			  return a.len() > b.len();
		  });
	long long ans = 0;
	for (int i = 0; i < k - 1; i++) {
		ans += segs[i].len();
	}
	return ans;
}

std::pair<std::vector<seg_t>, std::vector<seg_t>> filter_contain(std::vector<seg_t> segs)
{
	std::vector<seg_t> good_seg, bad_seg;
	std::sort(segs.begin(), segs.end(), [](const seg_t &a, const seg_t &b)
		  {
			  if (a.r != b.r) {
				  return a.r < b.r;
			  } else {
				  return a.l > b.l;
			  }
		  });
	int last_l = -1;
	for (auto s : segs) {
		if (s.l <= last_l) {
			bad_seg.emplace_back(s);
		} else {
			good_seg.emplace_back(s);
			last_l = s.l;
		}
	}
	return {good_seg, bad_seg};
}

long long solve2(size_t k, std::vector<seg_t> segs)
{
	auto [good_seg, bad_seg] = filter_contain(std::move(segs));
	std::sort(bad_seg.begin(), bad_seg.end(), [](const seg_t &a, const seg_t &b)
		  {
			  return a.len() > b.len();
		  });

	std::vector<long long> w;
	for (size_t i = 1; i < good_seg.size(); i++) {
		w.emplace_back(-good_seg[i - 1].l + good_seg[i].r);
	}
	std::sort(w.begin(), w.end(), std::greater<>());
	std::vector<long long> f(k + 1), g(k + 1);
	for (size_t i = 0; i < k; i++) {
		if (i < w.size()) {
			f[i + 1] = f[i] + w[i];
		}
		if (i < bad_seg.size()) {
			g[i + 1] = g[i] + bad_seg[i].len();
		}
	}

	auto ans = std::numeric_limits<long long>::min();
	for (int i = 1; i <= k; i++) {
		ans = std::max(ans, f[i - 1] + good_seg[0].r - good_seg.back().l + g[k - i]);
	}
	return ans;
}