题解

代码：

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

vector<int> X;            // 离散化后的坐标
vector<int> cover, len;   // 线段树：覆盖次数、被覆盖长度
int S;                    // X 的大小，叶节点区间数为 S-1

// 线段树区间更新
void update(int node, int tl, int tr, int l, int r, int val) {
    if (l > r || l > tr || r < tl) return;
    if (l <= tl && tr <= r) {
        cover[node] += val;
        if (cover[node] > 0)
            len[node] = X[tr + 1] - X[tl];
        else
            len[node] = (tl == tr) ? 0 : len[node * 2] + len[node * 2 + 1];
        return;
    }
    int tm = (tl + tr) / 2;
    update(node * 2, tl, tm, l, r, val);
    update(node * 2 + 1, tm + 1, tr, l, r, val);
    if (cover[node] == 0)
        len[node] = len[node * 2] + len[node * 2 + 1];
}

// 在实际坐标 [L, R) 上增加覆盖次数 val
void update_range(int L, int R, int val) {
    if (L >= R) return;
    int l = lower_bound(X.begin(), X.end(), L) - X.begin();
    int r = lower_bound(X.begin(), X.end(), R) - X.begin() - 1;
    if (l <= r) update(1, 0, S - 2, l, r, val);
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    vector<int> A, B;       // 有效路径（去掉 a == b 的退化路径）
    vector<int> pts;        // 所有端点
    for (int i = 0; i < n; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        if (a < b) {        // 退化路径始终可以选点弧，不影响答案
            A.push_back(a);
            B.push_back(b);
            pts.push_back(a);
            pts.push_back(b);
        }
    }

    // 没有有效路径，答案为 0
    if (pts.empty()) {
        printf("0\n");
        return 0;
    }

    // 端点排序去重
    sort(pts.begin(), pts.end());
    pts.erase(unique(pts.begin(), pts.end()), pts.end());
    int K = pts.size();

    // 离散化坐标：所有端点 + 0 + m
    X = pts;
    X.push_back(0);
    X.push_back(m);
    sort(X.begin(), X.end());
    X.erase(unique(X.begin(), X.end()), X.end());
    S = X.size();

    cover.assign(4 * S, 0);
    len.assign(4 * S, 0);

    int N_eff = A.size();
    // 初始状态：所有点对都选不跨过 0 的弧 [a, b]
    for (int i = 0; i < N_eff; ++i)
        update_range(A[i], B[i], 1);

    int ans = len[1];   // 根节点长度即为当前并集长度

    // 每个端点处的事件
    vector<vector<int>> enter(K), leave(K);
    for (int i = 0; i < N_eff; ++i) {
        int pa = lower_bound(pts.begin(), pts.end(), A[i]) - pts.begin();
        enter[pa].push_back(i);
        int pb = lower_bound(pts.begin(), pts.end(), B[i]) - pts.begin();
        leave[pb].push_back(i);
    }

    // 按顺时针顺序扫描所有端点
    for (int j = 0; j < K; ++j) {
        // 处理进入事件：x 跨过 a_i，S_i 从 0 变 1
        for (int i : enter[j]) {
            update_range(A[i], B[i], -1);
            update_range(B[i], m, 1);
            update_range(0, A[i], 1);
        }
        // 处理离开事件：x 跨过 b_i，S_i 从 1 变 0
        for (int i : leave[j]) {
            update_range(B[i], m, -1);
            update_range(0, A[i], -1);
            update_range(A[i], B[i], 1);
        }
        if (len[1] < ans) ans = len[1];
    }

    printf("%d\n", ans);
    return 0;
}