思维：线段树dp

Posted on | In

https://ac.nowcoder.com/acm/contest/881/I

不得不说这题是真的难，看题解都差点没用理解。）

给定平面上若干（1e5）点，每个点ab两个权值，要求将其分为两组，a组的a权值和加b组的b权值和最大，划分条件转化一下就是，不能有a出现在b的右下，也就是要找到一条不降的折线，其上是a，其下是b。我们认为位于折线上的那些点属于b。

暴力dp是可做的，离散化xy并枚举每一列的划分点。考虑优化，认为dp[i]表示，加入i点后，如果折线的最后一个转折点是i，那么总和的最大值。它该怎么更新呢，对于点1~i-1，如果它们比i低，那折线就可以从它们那里拐过来，然后再加上b[i]；同时，再加入i点后，其余的dp值也需更新，比i高的折线会把i看作b，比i低的折线会把i看作a，分别加上这两个值即可。

这里我们注意到，已经用到了单点修改、区间加、询问区间最大值的操作，就果断线段树，将y离散化后在y上建立线段树，也就是dp数组是用线段树实现的。注意需要考虑x轴，这样一条会把所有点视为a的折线，建线段树的时候按1，1+tot范围去建立即可。

代码

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

*/