思维：线段树dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lson (o<<1)
#define rson (o<<1|1)
const int maxn=1e5+4;
struct point{
    int x,y;
    ll a,b;
    friend bool operator<(const point& u,const point& v){
        if(u.x!=v.x){
            return u.x<v.x;
        }else
            return u.y>v.y;
    }
}ps[maxn];
int _y[maxn];

ll val[maxn<<2],lazy[maxn<<2];  //val维护线段树区间最大值,dp融入其中了

void build(int o,int l,int r){
    val[o]=0;
    lazy[o]=0;
    if(l==r)
        return ;
    int mid=(l+r)/2;
    build(lson,l,mid);
    build(rson,mid+1,r);
}
void pushup(int o){
    val[o]=max(val[lson],val[rson]);
}
void pushdown(int o){
    if(lazy[o]){
        val[lson]+=lazy[o];
        val[rson]+=lazy[o];
        lazy[lson]+=lazy[o];
        lazy[rson]+=lazy[o];
        lazy[o]=0;
    }
}
void update1(int o,int l,int r,int L,int R,ll add){
    //区间增加
    if(l>=L&&r<=R){
        val[o]+=add;
        lazy[o]+=add;
        return ;
    }
    pushdown(o);
    int mid=(l+r)/2;
    if(L<=mid){
        update1(lson,l,mid,L,R,add);
    }
    if(R>mid){
        update1(rson,mid+1,r,L,R,add);
    }
    pushup(o);
}
void update2(int o,int l,int r,int pos,ll x){
    //单点修改
    if(l==r){
        val[o]=max(x,val[o]);
        return;
    }
    pushdown(o);
    int mid=(l+r)/2;
    if(pos<=mid){
        update2(lson,l,mid,pos,x);
    }else{
        update2(rson,mid+1,r,pos,x);
    }
    pushup(o);
}
ll query(int o,int l,int r,int L,int R){
    if(l>=L&&r<=R){
        return val[o];
    }
    pushdown(o);
    int mid=(l+r)/2;
    ll res=0;
    if(L<=mid){
        res=max(res,query(lson,l,mid,L,R));
    }
    if(R>mid){
        res=max(res,query(rson,mid+1,r,L,R));
    }
    return res;
}

int n;
int main(){
    while(cin>>n){
        for(int i=1;i<=n;i++){
            cin>>ps[i].x>>ps[i].y>>ps[i].a>>ps[i].b;
            _y[i]=ps[i].y;
        }
        sort(_y+1,_y+n+1);
        int tot=unique(_y+1,_y+1+n)-_y-1;
        for(int i=1;i<=n;i++){
            ps[i].y=lower_bound(_y+1,_y+tot+1,ps[i].y)-_y+1;  //从2开始计数，1留给x轴
        }
        sort(ps+1,ps+1+n);
        build(1,1,tot+1);
        for(int i=1;i<=n;i++){
            ll dpi=query(1,1,tot+1,1,ps[i].y)+ps[i].b;
            update2(1,1,tot+1,ps[i].y,dpi);
            update1(1,1,tot+1,1,ps[i].y-1,ps[i].a);
            if(ps[i].y<tot+1)
                update1(1,1,tot+1,ps[i].y+1,tot+1,ps[i].b);

        }
        cout<<val[1]<<endl;
    }
}
/*
3
1 1 1 2
2 2 2 1
3 3 1 2

*/