树状数组

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

const int N = 100010, inf = 2147483647;
int n, p, tot, len;
int tr[N * 2], f[N];

void add(int x, int k) {
    for (int i = x; i <= len; i += i & -i)
        tr[i] = min(tr[i], k);
}

int qry(int x) {
    int res = inf;
    for (int i = x; i; i -= i & -i) res = min(res, tr[i]);
    return res;
}

struct Point {
    int x, y, v, id;
} T[2 * N];

bool cmp(Point a, Point b) {
    if (a.x != b.x) return a.x < b.x;
    if (a.y != b.y) return a.y < b.y;
    return a.v < b.v;
}

int main() {
    scanf("%d%d", &n, &p);
    vector<int> vv;
    map<int, int> ma;
    vv.push_back(0);
    vv.push_back(n);
    for (int i = 1; i <= p; i ++ ) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        vv.push_back(y1), vv.push_back(y2);
        if (x1 == x2 && y1 == y2) continue;
        T[++ tot] = {x1, y1, 1, i};
        T[++ tot] = {x2, y2, 0, i}; 
    }
    sort(vv.begin(), vv.end());
    len = unique(vv.begin(), vv.end()) - vv.begin();
    for (int i = 0; i < len; i ++ ) ma[vv[i]] = i + 1;
    T[++ tot] = {n, n, 1, p + 1};
    T[++ tot] = {0, 0, 0, 0};
    sort(T + 1, T + tot + 1, cmp);
    for (int i = 1; i <= len; i ++ ) tr[i] = inf;
    for (int i = tot; i >= 1; i -- ) {
        if (T[i].v == 0) {
            f[T[i].id] = qry(len - ma[T[i].y] + 1) - T[i].x - T[i].y;
        } else {
            add(len - ma[T[i].y] + 1, T[i].x + T[i].y + f[T[i].id]);
        }
    }
    printf("%d\n", f[0]);
    return 0;
}