Description
公交车一共经过N（1<=N<=20000）个站点，从站点1一直驶到站点N。K（1<=K<=50000)群奶牛希望搭乘这辆公交车。第i群牛一共有Mi（1<=Mi<=N)只.
他们希望从Si到Ei去。
公交车只能座C（1<=C<=100）只奶牛。而且不走重复路线，请计算这辆车最多能满足多少奶牛听要求。
注意：对于每一群奶牛，可以部分满足，也可以全部满足，也可以全部不满足。
Input
第1行： 三个整数： K，N，C。 由空格隔开。
第2..K+1行：第i+1行，告诉你第i组奶牛的信息： S_i, E_i and M_i。由空格隔开。
Output
一行：可以在庙会乘坐捷运的牛的最大头数
HINT
捷运可以把2头奶牛从展台1送到展台5，3头奶牛从展台5到展台8， 2头奶牛从展台8 到展台14，1头奶牛从展台9送到展台12，一头奶牛从展台13送到展台14， 一头奶牛从 14送到15。
题目分析
这种“线段贪心”，最经典的莫过于容量为1的情况。
容量为1时，做法就是按照右端点排序，$O(n)$扫一遍选取不冲突的线段。这个贪心之所以不需要“反悔”，是因为价值和容量一一对应：每一时刻不论选哪一条线段，获得价值都是1.从这个角度上来说，所有线段是无差别的。
想法自然但不正确的贪心1
从容量为1的情况会想到：既然答案可以看做是c次互不影响的“容量为1”路径，那就做c次$O(n)$的贪心嘛。
上图中，最优决策的确可以看做是c次互不影响的决策。但是当我们去选取线段时，会发现按照r端点排序的贪心策略在分配c组互不影响的决策上失效了。
依然按照r排序的正确贪心2
这里采用一种非形式化的语言描述这种贪心策略的正确性：
对于总的安排来说，目标是让每一时刻容量都不要空闲；对于细的策略来说，因为这里线段可以拆开，所以目标是让选取的线段越少冲突越好。
那么先按照r排序。排序后，当然是越靠前的线段越“好”。这里的“好”指的是，这条线段既把之前的容量利用起来；又对后面的线段产生较小的影响。
实在不行可以假设这个结论就是对的……
那么我是用永久标记线段树来维护这个贪心过程。
#include<bits/stdc++.h>
const int maxn = ; struct node
{
int l,r,v;
bool operator < (node a) const
{
return r < a.r;
}
}edges[maxn];
int k,n,c,ans;
int f[maxn<<],add[maxn<<]; int read()
{
char ch = getchar();
int num = ;
bool fl = ;
for (; !isdigit(ch); ch=getchar())
if (ch=='-') fl = ;
for (; isdigit(ch); ch=getchar())
num = (num<<)+(num<<)+ch-;
if (fl) num = -num;
return num;
}
int query(int rt, int L, int R, int l, int r, int hd)
{
if (L <= l&&r <= R){
return f[rt]+hd;
}
int mid = (l+r)>>, ans = ;
if (L <= mid) ans = std::max(query(rt<<, L, R, l, mid, hd+add[rt]), ans);
if (R > mid) ans = std::max(query(rt<<|, L, R, mid+, r, hd+add[rt]), ans);
return ans;
}
void pushup(int rt)
{
f[rt] = std::max(f[rt<<], f[rt<<|])+add[rt];
}
void adds(int rt, int L, int R, int l, int r, int c)
{
if (L <= l&&r <= R){
f[rt] += c, add[rt] += c;
return;
}
int mid = (l+r)>>;
if (L <= mid) adds(rt<<, L, R, l, mid, c);
if (R > mid) adds(rt<<|, L, R, mid+, r, c);
pushup(rt);
}
int main()
{
k = read(), n = read(), c = read();
for (int i=; i<=k; i++)
edges[i].l = read(), edges[i].r = read(), edges[i].v = read();
std::sort(edges+, edges+k+);
for (int i=; i<=k; i++)
{
int delta = std::min(c-query(, edges[i].l, edges[i].r, , n, ), edges[i].v);
ans += delta;
if (delta)
adds(, edges[i].l, edges[i].r-, , n, delta);
}
printf("%d\n",ans);
return ;
}
END