Solution

这个题的转换还是有难度的。

我们观察一下，对于可以包含其他区间的大区间，要使得答案最优无非就是两种分组方式：单独一组或者与被包含的区间一组。因为根据题意，如果有多个区间，添加区间实际上是添加限制，会使得答案变小，于是能包含其他区间的这些区间实际上是可以独立出来的，我们把这部分区间去掉，观察剩下的区间有什么性质。

将剩下的这部分区间按左右端点双关键字排序，那么从左到右区间的左端点是单调不降的，又由于前面将大区间都去掉了，所以实际上右端点也是单调不降的，这个性质就非常好了，如果我们选择了某两个区间​​​分到一组，那么这一组的贡献显然是​​，对于中间的任意一个区间​​，由前面的分析可以得出，​​，​​，因此与都是被​​包含的，那么贪心地想，我们当然是将这一段区间都划分到一组。

设​表示分组用了前个线段的最优解，就可以写出如下转移方程：

很明显，​​这个东西可以用单调队列来维护，我们只需要将从小到大枚举，然后从大到小枚举避免后效性，对每个维护一个单调队列即可，维护的最大值，从队尾把的都弹掉，这样总时间复杂度是。

最后就枚举一下这些小区间被分了多少组，不足k组就用大区间单独成组来补全，统计最大答案。

Code

struct Node {
    int l, r;
    bool operator <(const Node s)const { return l < s.l || (l == s.l && r > s.r); }
}s[N], a[N];
int seg[N], dp[N][N], q[N][N], head[N], tail[N];

int main() {
    int n = fast_IO::read(), k = fast_IO::read(), m = 0, tot = 0;
    for (int i = 1; i <= n; ++i)
        s[i].l = fast_IO::read(), s[i].r = fast_IO::read();
    sort(s + 1, s + n + 1);
    int maxr = INF;
    for (int i = n; i; --i) {
        if (s[i].r >= maxr)seg[++tot] = s[i].r - s[i].l;
        else maxr = s[i].r, a[++m] = s[i];
    }
    sort(a + 1, a + m + 1);
    sort(seg + 1, seg + tot + 1, greater<int>());
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    q[0][head[0]++] = 0;
    for (int j = 1; j <= m; ++j) {
        for (int i = k; i; --i) {
            while (head[i - 1] != tail[i - 1] && a[q[i - 1][tail[i - 1]] + 1].r <= a[j].l)++tail[i - 1];
            if (head[i - 1] != tail[i - 1])dp[i][j] = dp[i - 1][q[i - 1][tail[i - 1]]] + a[q[i - 1][tail[i - 1]] + 1].r - a[j].l;
            if (~dp[i][j]) {
                while (head[i] != tail[i] && dp[i][j] + a[j + 1].r >= dp[i][q[i][head[i] - 1]] + a[q[i][head[i] - 1] + 1].r)--head[i];
                q[i][head[i]++] = j;
            }
        }
    }
    int ans = 0, sum = 0;
    for (int i = 0; i <= k && i <= tot; ++i) {
        sum += seg[i];
        if (~dp[k - i][m])
            ans = max(ans, dp[k - i][m] + sum);
    }
    printf("%d", ans);
    return 0;
}