本文共 3170 字，大约阅读时间需要 10 分钟。
题目链接
题意
给你\(n\)个点，每个点的坐标为\((x_i,y_i)\)，有两个权值\(a_i,b_i\)。
现在要你将它分成
\(\mathbb{A},\mathbb{B}\)两部分，使得在满足“
\(\mathbb{A}\)的点不能落在在
\(\mathbb{B}\)的点的右下方”的条件下
\(\sum\limits_{i\in\mathbb{A}}a_i+\sum\limits_{j\in\mathbb{B}}b_j\)最大。
思路
讲得很详细，大家可以看这位大佬的昂~
代码实现如下
#include #include
vec;struct Point { int x, y, a, b; bool operator < (const Point& pp) const { return x == pp.x ? y > pp.y : x < pp.x; }}point[maxn];struct node { int l, r; LL mx, lazy;}segtree[maxn<<2];void push_up(int rt) { segtree[rt].mx = max(segtree[lson].mx, segtree[rson].mx);}void push_down(int rt) { LL x = segtree[rt].lazy; segtree[rt].lazy = 0; segtree[lson].lazy += x; segtree[rson].lazy += x; segtree[lson].mx += x; segtree[rson].mx += x;}void build(int rt, int l, int r) { segtree[rt].l = l, segtree[rt].r = r; segtree[rt].mx = segtree[rt].lazy = 0; if(l == r) return; int mid = (segtree[rt].l + segtree[rt].r) >> 1; build(lson, l, mid); build(rson, mid + 1, r);}void update1(int rt, int pos, LL val) { if(segtree[rt].l == segtree[rt].r) { segtree[rt].mx = val; return; } push_down(rt); int mid = (segtree[rt].l + segtree[rt].r) >> 1; if(pos <= mid) update1(lson, pos, val); else update1(rson, pos, val); push_up(rt);}void update2(int rt, int l, int r, LL val) { if(segtree[rt].l == l && segtree[rt].r == r) { segtree[rt].mx += val; segtree[rt].lazy += val; return; } push_down(rt); int mid = (segtree[rt].l + segtree[rt].r) >> 1; if(r <= mid) update2(lson, l, r, val); else if(l > mid) update2(rson, l, r, val); else { update2(lson, l, mid, val); update2(rson, mid + 1, r, val); } push_up(rt);}LL query(int rt, int l, int r) { if(segtree[rt].l == l && segtree[rt].r == r) { return segtree[rt].mx; } push_down(rt); int mid = (segtree[rt].l + segtree[rt].r) >> 1; if(r <= mid) return query(lson, l, r); else if(l > mid) return query(rson, l, r); else return max(query(lson, l, mid), query(rson, mid + 1, r));}int main() {#ifndef ONLINE_JUDGEFIN;#endif // ONLINE_JUDGE while(~scanf("%d", &n)) { vec.clear(); for(int i = 1; i <= n; ++i) { scanf("%d%d%d%d", &point[i].x, &point[i].y, &point[i].a, &point[i].b); vec.push_back(point[i].y); } sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end()); sort(point + 1, point + n + 1); for(int i = 1; i <= n; ++i) { point[i].y = lower_bound(vec.begin(), vec.end(), point[i].y) - vec.begin() + 1; } int sz = vec.size(); build(1, 0, sz + 1); for(int i = 1; i <= n; ++i) { LL num = query(1, 0, point[i].y); update1(1, point[i].y, num + point[i].b); update2(1, 0, point[i].y - 1, point[i].a); update2(1, point[i].y + 1, sz + 1, point[i].b); } printf("%lld\n", segtree[1].mx); } return 0;}