P1607 [USACO09FEB]Fair Shuttle G

题意

现在又n头牛，分成了k组，每一组有三个值，s、e、m，分别表示，这一组牛从s到e，并且这一组里面有m头牛，现在有一辆车，一次只能装c头牛，并且是从1号位置开到n号位置，单向开，现在问你最多有多少头牛能够乘坐车从它的起始位置到它的终点位置。

思路

贪心+线段树
贪心：将奶牛的起终点按照终点从小到大排序，如果终点相同，将起点按照从小到大排序。
线段树：求某段区间内最多能载多少头奶牛。
假设当前的车上的牛已经满了，如果我们将之前的牛提出，那么就不能将它们送到终点，这样得到的结果肯定会小，那么，如果当前的要上车的奶牛要上车，但是它的目的地非常远，那么对后面的目的地比当前牛的目的地更近的牛是非常不利的，所以我们要按照这样的规则排序。

#include <bits/stdc++.h>#define int long long
#define x first
#define y secondusing namespace std;const int N = 2e5 + 10;
typedef pair<int, int> PII;int n, k, c;struct Edge
{int s, e, m;bool operator < (const Edge &t) const{if (e == t.e) return s < t.s;return e < t.e;}
}cow[N << 1];struct node
{int l, r;int maxx;int tag;
}tr[N << 2];void pushup(int u) { tr[u].maxx = max(tr[u << 1].maxx, tr[u << 1 | 1].maxx); }void pushdown(int u)
{if (tr[u].tag){tr[u << 1].maxx += tr[u].tag;tr[u << 1].tag += tr[u].tag;tr[u << 1 | 1].maxx += tr[u].tag;tr[u << 1 | 1].tag += tr[u].tag;tr[u].tag = 0;}
}void build(int u, int l, int r)
{tr[u] = {l, r, 0, 0};if (l == r) return ;int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);
}void modify(int u, int l, int r, int k)
{if (l <= tr[u].l && r >= tr[u].r){tr[u].tag += k;tr[u].maxx += k;return ;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if (l <= mid) modify(u << 1, l, r, k);if (r > mid) modify(u << 1 | 1, l, r, k);pushup(u);
}int query(int u, int l, int r)
{if (l <= tr[u].l && r >= tr[u].r) return tr[u].maxx;pushdown(u);int mid = tr[u].l + tr[u].r >> 1;int ans = 0;if (l <= mid) ans = query(u << 1, l, r);if (r > mid) ans = max(ans, query(u << 1 | 1, l, r));return ans;
}void solve()
{cin >> k >> n >> c;for (int i = 1; i <= k; i ++){cin >> cow[i].s >> cow[i].e >> cow[i].m;cow[i].e --;}build(1, 1, n);sort(cow + 1, cow + 1 + k);int ans = 0;for (int i = 1; i <= k; i ++){int tmp = query(1, cow[i].s, cow[i].e);if (tmp < c){int t = min(c - tmp, cow[i].m);ans += t;modify(1, cow[i].s, cow[i].e, t);}}cout << ans << endl;
}signed main()
{std::ios::sync_with_stdio(false);solve();return 0;
}