大致题意：给你n个点，第i个点在的位置为(xi,yi)，有两个属性值(ai,bi)。现在让你把这n个点划分为A和B两个部分，使得最后不存在i∈A和j∈B，使得xi>=xj且yi<=yj。然后对于所有的划分方法，找到并输出

                                                                

首先那个划分的限制条件看起来复杂，其实就是A中不存在点在B中任意一个点的右下角。根据这个限制，显然对于任意合法的划分，我都可以找到一条不下降的折线把所有点划分为两个部分。左上部分为A，右下部分为B。我们不妨移动这个折线，使得B中的部分点在边界上。如下图，是一种合法的方案。

                                                       

现在要求的是两部分和的最大值，我们考虑DP。设dp[i]表示到目前为止，第i个点在折线上时的和的最大值。然后考虑每增加一个点会产生什么贡献。显然，增加一个点i之后，对于之前考虑过的比他高的点，他应该在B中，他的贡献是bi；相反，对于那些比他低的点，他应该在A中，他的贡献就是ai。于是，我们可以动态维护dp的数值，对于一个新加入的点i有：

                                            

另外，对于当前点i，此时当他在折线上时的最大值为：

                                                          

具体到这道题，由于增加一个点产生的贡献其实是对区间的影响，然后转移的时候也需要求区间的最大值，所以我们可以把y坐标离散化并建立一棵线段树，维护区间最大值。需要注意的是，我们需要虚拟一个高度为0的点作为第一个点的参照。具体见代码： 

#include <bits/stdc++.h> #define INF 0x3f3f3f3f3f3f3f3fll #define LL long long #define sc(x) scanf("%d",&x) #define scc(x,y) scanf("%d%d",&x,&y) #define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z) #define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout); using namespace std; const int N = 1e5 + 10; struct node{int x,y,a,b;} p[N]; int n,m,num[N],tot; struct ST { #define ls i<<1 #define rs i<<1|1     struct node     {         LL max,lazy;
        int l,r;
    } T[N<<2];

    inline void push_up(int i)     {
        T[i].max=max(T[ls].max,T[rs].max);
    }

    void build(int i,int l,int r)     {
        T[i]=node{0,0,l,r};
        if (l==r)
        {
            T[i].max=-INF;
            T[i].lazy=0;
            return;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        push_up(i);
    }

    inline void push_down(int i)     {
        T[ls].lazy+=T[i].lazy;
        T[rs].lazy+=T[i].lazy;
        T[ls].max+=T[i].lazy;
        T[rs].max+=T[i].lazy;
        T[i].lazy=0;
    }

    void update(int i,int l,int r,LL x)     {
     if (l>r) return;
        if ((T[i].l==l)&&(T[i].r==r))
        {
            T[i].lazy+=x;
            T[i].max+=x;
            return;
        }
        if (T[i].lazy!=0) push_down(i);
        int mid=(T[i].l+T[i].r)>>1;
        if (mid>=r) update(ls,l,r,x);
        else if (mid<l) update(rs,l,r,x);
        else         {
            update(ls,l,mid,x);
            update(rs,mid+1,r,x);
        }
        push_up(i);
    }

    void upd(int i,int pos,LL x)     {
        if (T[i].l==T[i].r)
        {
            T[i].max=max(T[i].max,x);
            return;
        }
        if (T[i].lazy!=0) push_down(i);
        int mid=(T[i].l+T[i].r)>>1;
        if (mid>=pos) upd(ls,pos,x); else upd(rs,pos,x);
        push_up(i);
    }

    LL getmax(int i,int l,int r)     {
     if (l>r) return 0;
        if ((T[i].l==l)&&(T[i].r==r)) return T[i].max;
        if (T[i].lazy!=0) push_down(i);
        int mid=(T[i].l+T[i].r)>>1;
        if (mid>=r) return getmax(ls,l,r);
        else if (mid<l) return getmax(rs,l,r);
        else return max(getmax(ls,l,mid),getmax(rs,mid+1,r));
    }

} seg; inline bool cmp(node a,node b) { return a.x==b.x?a.y>b.y:a.x<b.x;
} int main() { while(~sc(n))
    {
        tot=0; for(int i=1;i<=n;i++)
        {
            scc(p[i].x,p[i].y);
            scc(p[i].a,p[i].b);
            num[++tot]=p[i].y;
        }
        sort(num+1,num+1+tot);
        tot=unique(num+1,num+1+tot)-num-1; for(int i=1;i<=n;i++)
            p[i].y=lower_bound(num+1,num+1+tot,p[i].y)-num+1;
        tot++; sort(p+1,p+1+n,cmp);
        seg.build(1,1,tot);
        seg.upd(1,1,0); for(int i=1;i<=n;i++)
        {
            LL cur=seg.getmax(1,1,p[i].y);
            seg.upd(1,p[i].y,cur+p[i].b);
            seg.update(1,p[i].y+1,tot,p[i].b);
            seg.update(1,1,p[i].y-1,p[i].a);
        } printf("%lld\n",seg.T[1].max);
    } return 0;
}