C32 线段树+贪心 P1607 [USACO09FEB] Fair Shuttle G

// 贪心+线段树 O(nlogn)
#include <bits/stdc++.h>
using namespace std;
#define ls p << 1
#define rs p << 1 | 1
#define mid (tr[p].l + tr[p].r) / 2
const int N = 5e4 + 10;
int n, k, c, ans;
struct line
{
    int l, r, m;
    bool operator<(line &b) { return r < b.r; }
} s[N]; // 区间
struct trnode{int l, r, mx, lazy;} tr[N << 2];
void pushup(int p) { tr[p].mx = max(tr[ls].mx, tr[rs].mx); }
void pushdown(int p)
{
    if (tr[p].lazy)
    {
        tr[ls].mx += tr[p].lazy;
        tr[rs].mx += tr[p].lazy;
        tr[ls].lazy += tr[p].lazy;
        tr[rs].lazy += tr[p].lazy;
        tr[p].lazy = 0;
    }
}
void build(int p, int l, int r)
{ // 建树
    tr[p] = trnode{l, r, 0, 0};
    if (l == r)return;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(p);
}
void change(int p, int l, int r, int v)
{

    if (l <= tr[p].l && tr[p].r <= r)
    {
        tr[p].mx += v;
        tr[p].lazy += v;
        return;
    }
    pushdown(p);
    if(l <= mid)change(ls, l, r, v);
    if(r > mid)change(rs, l, r, v);
    pushup(p);
}
int query(int p, int l, int r)
{
    if (l <= tr[p].l && tr[p].r <= r)return tr[p].mx;
    pushdown(p);
    int res=0;
    if(l <= mid) res=max(res, query(ls, l, r));
    if(r > mid) res=max(res, query(rs, l, r));
    return res;
}
int main()
{
    scanf("%d%d%d", &k, &n, &c);
    for (int i = 1; i <= k; i++)scanf("%d%d%d", &s[i].l, &s[i].r, &s[i].m);
    sort(s + 1, s + k + 1); // 按右端排序
    build(1, 1, n);
    for (int i = 1; i <= k; i++)
    {
        int l = s[i].l, r = s[i].r, m = s[i].m;
        int mx = query(1, l, r - 1);
        int x = min(c - mx, m); // 能上车的牛数
        change(1, l, r - 1, x);
        ans += x;
    }
    printf("%d\n", ans);
    return 0;
}