2019牛客多校第一场 I Points Division（动态规划+线段树）

传送门：https://ac.nowcoder.com/acm/contest/881/I

题意：

给你n个点，每个点有两个属性a,b

需要将点划分为两堆，划分依据是对于在A划分中的任意点a和在B划分中的任意点b满足

不存在当a.x>b.x时,a.y<b.y 的情况

在A划分中的点可以给出其a属性的贡献，在B划分中的点可以给出其b属性的贡献

求最大贡献和

题解：

根据题意，我们可以得出结论，我们需要找的是一根折线，这根折线将点集分为A、B两部分、

我们需要求这两个部分的最大权值和

我们考虑dp状态

dp[i]表示到第i个点在折线上时和的最大值，如果增加了这个点，他对答案产生的贡献就是，对于之前比这个点高的点，对答案的贡献是ai，对于之前比这个点低的点，对答案的贡献是bi

于是$d p[j]=\left{\begin{array}{ll}{d p[j]+b_{i}} & {j<i, y_{j}>y_{i}} \ {d p[j]+a_{i}} & {j<i, y_{j}<y_{i}}\end{array}\right.$

$d p[i]=b_{i}+\max {1 \leq j<i, y{j}<y_{i}} d p[j]$

显然这个式子是可以用线段树维护区间最值的

因为值域范围为1e9，我们将y值离散化后建树，维护的区间最大值就是我们最后的答案

因为dp的值是从0开始的，所以我们建树也是从0开始

排序是为了能够有A，B的合法划分

感谢邱神的博客学习：https://blog.csdn.net/u013534123/article/details/96465704

代码：

1#include <set>
2#include <map>
3#include <cmath>
4#include <cstdio>
5#include <string>
6#include <vector>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10using namespace std;
11typedef long long LL;
12typedef pair<int, int> pii;
13typedef unsigned long long uLL;
14#define ls rt<<1
15#define rs rt<<1|1
16#define lson l,mid,rt<<1
17#define rson mid+1,r,rt<<1|1
18#define bug printf("*********\n")
19#define FIN freopen("input.txt","r",stdin);
20#define FON freopen("output.txt","w+",stdout);
21#define IO ios::sync_with_stdio(false),cin.tie(0)
22#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"
23#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"
24#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"
25const int maxn = 3e5 + 5;
26const int INF = 0x3f3f3f3f;
27const int mod = 1e9 + 7;
28LL quick_pow(LL x, LL y) {
29    LL ans = 1;
30    while(y) {
31        if(y & 1) {
32            ans = ans * x % mod;
33        } x = x * x % mod;
34        y >>= 1;
35    } return ans;
36}
37LL Max[maxn << 2];
38LL lazy[maxn << 2];
39void push_up(int rt) {
40    Max[rt] = max(Max[ls], Max[rs]);
41}
42void build(int l, int r, int rt) {
43    Max[rt] = lazy[rt] = 0;
44    if(l == r) return;
45    int mid = (l + r) >> 1;
46    build(lson);
47    build(rson);
48}
49void push_down(int rt) {
50    if(lazy[rt]) {
51        lazy[ls] += lazy[rt];
52        lazy[rs] += lazy[rt];
53        Max[ls] += lazy[rt];
54        Max[rs] += lazy[rt];
55        lazy[rt] = 0;
56    }
57}
58void update(int L, int R, LL val, int l, int r, int rt) {
59    if(L <= l && r <= R) {
60        Max[rt] += val;
61        lazy[rt] += val;
62        return;
63    }
64    push_down(rt);
65    int mid = (l + r) >> 1;
66    if(L <= mid) update(L, R, val, lson);
67    if(R > mid) update(L, R, val, rson);
68    push_up(rt);
69}
70void change(int pos, LL val, int l, int r, int rt) {
71    if(l == r) {
72        Max[rt] =  val;
73        return;
74    }
75    push_down(rt);
76    int mid = (l + r) >> 1;
77    if(pos <= mid) change(pos, val, lson);
78    else change(pos, val, rson);
79    push_up(rt);
80}
81LL query(int L, int R, int l, int r, int rt) {
82    if(L <= l && r <= R) {
83        return Max[rt];
84    }
85    push_down(rt);
86    int mid = (l + r) >> 1;
87    LL ans = 0;
88    if(L <= mid) ans = max(ans, query(L, R, lson));
89    if(R > mid) ans = max(ans, query(L, R, rson));
90    return ans;
91}
92struct node {
93    int x, y, a, b;
94} p[maxn];
95bool cmp(node a, node b) {
96    if(a.x != b.x) return a.x < b.x;
97    return a.y > b.y;
98}
99int main() {
100#ifndef ONLINE_JUDGE
101    FIN
102#endif
103    int n;
104    while(~scanf("%d", &n)) {
105        vector<int> vec;
106        for(int i = 1; i <= n; i++) {
107            scanf("%d%d%d%d", &p[i].x, &p[i].y, &p[i].a, &p[i].b);
108            vec.push_back(p[i].y);
109        }
110        sort(vec.begin(), vec.end());
111        vec.erase(unique(vec.begin(), vec.end()), vec.end());
112        for(int i = 1; i <= n; i++) {
113            p[i].y = lower_bound(vec.begin(), vec.end(), p[i].y) - vec.begin() + 1;
114        }
115        int tot = vec.size();
116        sort(p + 1, p + n + 1, cmp);
117        build(0, tot, 1);
118        for(int i = 1; i <= n; i++) {
119            change(p[i].y, query(0, p[i].y, 0, tot, 1) + p[i].b, 0, tot, 1);
120            if(p[i].y - 1 >= 0) update(0, p[i].y - 1, p[i].a, 0, tot, 1);
121            if(p[i].y + 1 <= tot) update(p[i].y + 1, tot, p[i].b, 0, tot, 1);
122        }
123        printf("%lld\n", Max[1]);
124    }
125
126
127    return 0;
128}