官方题解

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 400010;
struct Build {
    int f, id;  //起止标示，id号
    ll p, len;  //点及长度
} b[N];
ll dp[N];  // dp[i]表示到第i段到的最长值
bool cmp(Build u, Build v) {
    if (u.p == v.p)
        return u.f < v.f;
    return u.p < v.p;
}  //对所有的点排序
void in(ll &x) {
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    for (x = 0; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
}  //快读
int main() {
    //  freopen("build.in", "r", stdin);
    //  freopen("build.out", "w", stdout);
    int t;
    scanf("%d", &t);
    while (t--) {
        ll n, x, y;
        int k;
        scanf("%lld %d", &n, &k);
        for (int i = 1; i <= k; i++) {
            // scanf("%lld %lld", &x, &y);
            in(x), in(y);
            b[i * 2 - 1].f = 0;
            b[i * 2 - 1].p = x;
            b[i * 2 - 1].id = i;
            b[i * 2 - 1].len = y - x + 1;
            //拆分后的第i段的第1个点 （左端点）
            b[i * 2].f = 1;
            b[i * 2].p = y;
            b[i * 2].id = i;
            b[i * 2].len = y - x + 1;
            //拆分后的第i段的第2个点（右端点）
        }                                 //读取k段，然后进行拆分（一段拆成两个点）
        sort(b + 1, b + 2 * k + 1, cmp);  //对所有的点排序 （区间所有的端点进行排序）
        memset(dp, 0, sizeof dp);         // dp数组清零
        ll maxl = 0;                      //初始最大值
        for (int i = 1; i <= 2 * k; i++) {
            if (b[i].f == 0)  //判断当前点的标记是0还是1,0表示起始点，1则表示终点
                dp[b[i].id] = maxl + b[i].len;  //若是起始点，则更新到当这段的最大长度
            else
                maxl = max(maxl, dp[b[i].id]);  //若是终点，则更新最大值
        }
        ll ans = 0;
        for (int i = 1; i <= k; i++) ans = max(ans, dp[i]);  //比较最大值
        printf("%lld\n", ans);                               //输出
    }
    return 0;
}