题目描述
LYK在玩一个游戏。
有k群小怪兽想乘坐公交车。第i群小怪兽想从xi出发乘坐公交车到yi。但公交车的容量只有M，而且这辆公交车只会从1号点行驶到n号点。
LYK想让小怪兽们尽可能的到达自己想去的地方。它想知道最多能满足多少小怪兽的要求。
当然一群小怪兽没必要一起上下车，它们是可以被分开来的。
输入输出格式
输入格式：
第一行三个数k,n,M。
接下来k行每行3个数xi，yi和ci。其中ci表示第i群小怪兽的小怪兽数量。
输出格式：
一个数表示最多有多少只小怪兽能满足要求。
输入输出样例
输入样例#1：
3 5 3
1 3 4
3 5 2
1 5 3
输出样例#1：
5 样例解释
第一群的3只小怪兽在1号点上车，并在3号点下车。
第二群的2只小怪兽在3号点上车，5号点下车。
说明
对于30%的数据小怪兽的总数不超过10只，n<=10。
对于另外30%的数据k,n<=1000。
对于100%的数据1<=n<=20000，1<=k<=50000，1<=M<=100，1<=ci<=100，1<=xi<yi<=n。
/*luogu上做过的原题。USACO的庙会班车，做线段树的那段时间看过，一眼认出是原题，毕竟看过好几次。 贪心+线段树 类似于活动安排，先按右端点排个序，然后线段树维护区间最大值就好了。
为什么呢。
因为一段路上公交车中还能坐下的最大的人数为 容量-这段路上车内人数的最大值。
所以，用线段树维护区间最大值，在小怪物上车的时候查询坐车的这段区间的最大值，
然后用容量-得到的最大值，就是能上车的人数。
遵循能上多少是多少的原则，这样得出来肯定是最优解。
需要注意的是，updata的时候是更新到node[i].r-1,因为node[i].r的时候上车的那群小怪物已经下车了。
*/ #include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 50005
#define lson (root<<1)
#define rson (root<<1|1)
#define _max(a,b) a=a>b?a:b
using namespace std; int k,n,m,x,y,ans,tmp,val;
int tree[N<<],mark[N<<];
struct Node
{
int l,r,peo;
bool operator <(const Node &a)const
{
if(a.r!=r)return r<a.r;
return l>a.l;
}
}node[N]; inline void read(int &num)
{
char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar()){num=num*+c-'';};
} void pushdown(int root)
{
if(!mark[root]) return;
int k=mark[root];
tree[lson]+=k;tree[rson]+=k;
mark[lson]+=k;mark[rson]+=k;
mark[root]=;
} int query(int root,int l,int r,int L,int R)
{
if(l>R||r<L) return ;
if(L<=l&&r<=R) return tree[root];
int mid=(l+r)>>;
pushdown(root);
int a=query(lson,l,mid,L,R),b=query(rson,mid+,r,L,R);
tree[root]=_max(tree[lson],tree[rson]);
return _max(a,b);
} void updata(int root,int l,int r,int L,int R,int to)
{
if(l>R||r<L) return;
if(L<=l&&r<=R)
{
mark[root]+=to;
tree[root]+=to;
return;
}
pushdown(root);
int mid=(l+r)>>;
updata(lson,l,mid,L,R,to);
updata(rson,mid+,r,L,R,to);
tree[root]=_max(tree[lson],tree[rson]);
} void init()
{
read(k),read(n),read(m);
for(int i=;i<=k;i++)
{
read(node[i].l),read(node[i].r),read(node[i].peo);
}
sort(node+,node+k+);
for(int i=;i<=k;i++)
{
tmp=query(,,n,node[i].l,node[i].r);
if(tmp>=m) continue; //最大值超过了容量，一个人也坐不下了
if(tmp+node[i].peo<=m) val=node[i].peo; //当前这群小怪物可以全部坐下
else val=m-tmp; //不能全坐下，能坐几个算几个
ans+=val;
updata(,,n,node[i].l,node[i].r-,val); //是到r-1,不是r！
}
printf("%d",ans);
} int main()
{
freopen("bus.in","r",stdin);
freopen("bus.out","w",stdout);
init();
fclose(stdin);
fclose(stdout);
return ;
}