如题。写的是我第一眼的想法，$O(p^2)$ DP 偏序转移，用 CDQ 分治进行优化。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,p;
struct node{
int id,x1,y1,x2,y2,f;
}a[200005];
bool cmp1(node a,node b){
    if (a.x2==b.x2)return a.y2<b.y2;
    return a.x2<b.x2;
}
bool cmp2(node a,node b){
    if (a.x1==b.x1)return a.y1<b.y1;
    return a.x1<b.x1;
}
int ls[6000005],rs[6000005],t[6000005],cnt=1;
int lson(int rt){
    if (ls[rt])return ls[rt];
    else {
        ls[rt]=++cnt;
        return cnt;
    }
}
int rson(int rt){
    if (rs[rt])return rs[rt];
    else {
        rs[rt]=++cnt;
        return cnt;
    }
}
void add(int rt,int l,int r,int k,int x){
    if (l>k||r<k)return;
    if (l==r){
        t[rt]=x;return;
    }
    int mid=(l+r)/2;
    add(lson(rt),l,mid,k,x);
    add(rson(rt),mid+1,r,k,x);
    t[rt]=min(t[lson(rt)],t[rson(rt)]);
}
int sum(int rt,int l,int r,int L,int R){
    if (l>R||r<L)return 0;
    if (l>=L&&r<=R)return t[rt];
    int mid=(l+r)/2;
    return min(sum(lson(rt),l,mid,L,R),sum(rson(rt),mid+1,r,L,R));
}
void cdq(int l,int r){
    if (l==r)return;
    int mid=(l+r)/2;
    cdq(l,mid);
    sort(a+l,a+mid+1,cmp1);
    sort(a+mid+1,a+r+1,cmp2);
    for (int i=l,j=mid+1;j<=r;j++){
        while (i<=mid&&a[i].x2<=a[j].x1){
            add(1,0,n,a[i].y2,a[i].f-a[i].x2-a[i].y2);
            i++; 
        }
        a[j].f=min(a[j].f,a[j].x1+a[j].y1+sum(1,0,n,0,a[j].y1));
    }
    
    for (int i=l;i<=mid;i++){
        add(1,0,n,a[i].y2,0);
    }
    cdq(mid+1,r);
   
}
signed main(){
    cin>>n>>p;
    for (int i=1;i<=p;i++){
        cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2;
        a[i].f=a[i].x1+a[i].y1;
        a[i].id=i;
    }
    a[p+1].x1=a[p+1].x2=a[p+1].y1=a[p+1].y2=n;a[p+1].f=2*n;
    a[p+1].id=p+1;
    sort(a+1,a+2+p,cmp2);
    cdq(1,p+1);
    for (int i=1;i<=p+1;i++){
    if (a[i].id==p+1){
        cout<<a[i].f;return 0;
    }
    }
    return 0;
}