题解

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7, inf = 0x7fffffff;
int n, q, tot, dp[N], b[N<<1], t, c[N<<1];
struct P {
    int x, y, o, k;
    P() {}
    P(int x, int y, int o, int k) : x(x), y(y), o(o), k(k) {} 
    bool operator < (const P w) const {
        return x == w.x ? y < w.y : x < w.x;
    }
} p[N<<1];

void add(int x, int k) { 
    while (x <= t) c[x] = min(c[x], k), x += x & -x;
}
int ask(int x) {
    int k = inf;
    while (x) k = min(k, c[x]), x -= x & -x;
    return k;
}

int main() {
    cin>>n>>q;
	b[++t] = 0, b[++t] = n;
    p[++tot] = P(0, 0, 0, 0), p[++tot] = P(n, n, 1, q+ 1);
    for (int i = 1; i <= q; i++) {
    	int xa,ya,xb,yb;
    	cin>>xa>>ya>>xb>>yb;
        b[++t] =ya, b[++t] =yb;
        p[++tot] = P(xa, ya, 1, i), p[++tot] = P(xb,yb, 0, i);
    }
    sort(b + 1, b + t + 1), t = unique(b + 1, b + t + 1) - b - 1;
    for (int i = 1; i <= tot; i++)
        p[i].y = lower_bound(b + 1, b + t + 1, p[i].y) - b;
    sort(p + 1, p + tot + 1);
    for (int i = 1; i <= t; i++) c[i] = inf;
    
    for(int i=1;i<=tot;i++){
    	if(p[i].o)dp[p[i].k]=ask(p[i].y)+p[i].x+b[p[i].y]; 
    	else add(p[i].y,dp[p[i].k]-p[i].x-b[p[i].y]) ;
	}
	cout<<dp[q+1];
    return 0;
}

内存我击败花神，时间花神击败我