Description：

公交车一共经过 $N$ 个站点， $K$ 群奶牛希望搭乘这辆公交车。第 $i$ 群牛一共有 $M_i$ 希望从 $S_i$ 到 $E_i$ 去。

公交车只能座 $C$ 只奶牛。求这辆车最多能满足多少奶牛。

$1\leqslant n\leqslant 20000,1\leqslant k\leqslant50000$

Solution：

首先如果 $C=1$ ，那么就有一个经典的贪心模型是每次选能上车的下车最早的人上车，这个也是一样，把所有牛群按右端点排序，加入尽量多的牛，用线段树维护每个位置还能加多少牛，那么就可以用线段树区间减和区间取 $\min$ 来做了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int k,n,c;

#define MAXK 50010

struct cow

{

	int l,r,s;

}g[MAXK];

bool cmp_l(cow a,cow b){return a.r < b.r;}

#define MAXN 20010

struct node

{

	int lc,rc;

	int maxv,tag;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)

	{

		t[rt].maxv = c;

		return;

	}

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	t[rt].maxv = c;

	return;

}

void pushdown(int rt)

{

	if(t[rt].tag != 0)

	{

		t[t[rt].lc].maxv += t[rt].tag;t[t[rt].lc].tag += t[rt].tag;

		t[t[rt].rc].maxv += t[rt].tag;t[t[rt].rc].tag += t[rt].tag;

		t[rt].tag = 0;

	}

	return;

}

void add(int rt,int L,int R,int k,int l,int r)

{

	if(L <= l && r <= R)

	{

		t[rt].maxv += k;

		t[rt].tag += k;

		return;

	}

	pushdown(rt);

	if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

	if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

	t[rt].maxv = min(t[t[rt].lc].maxv,t[t[rt].rc].maxv);

	return;

}

int query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].maxv;

	pushdown(rt);

	int res = 0x3f3f3f3f;

	if(L <= mid)res = min(res,query(t[rt].lc,L,R,l,mid));

	if(R > mid)res = min(res,query(t[rt].rc,L,R,mid + 1,r));

	return res;

}

int main()

{

	scanf("%d%d%d",&k,&n,&c);

	build(root,1,n - 1);

	for(int i = 1;i <= k;++i)

	{

		scanf("%d%d%d",&g[i].l,&g[i].r,&g[i].s);

	}

	sort(g + 1,g + 1 + k,cmp_l);

	int ans = 0;

	for(int i = 1;i <= k;++i)

	{

		int w = min(query(root,g[i].l,g[i].r - 1,1,n - 1),g[i].s);

		ans += w;

		add(root,g[i].l,g[i].r - 1,-w,1,n - 1);

	}

	cout << ans << endl;

	return 0;

}