「USACO05OCT」Flying Right

题意：一架航班要从 $1$ 号机场到 $n$ 号机场来回飞一次，有 $k$ 群牛想要坐飞机，每群牛想要从一个机场飞到另一个机场，飞机可以任意在某个机场停留，带上部分或全体牛，飞机的客容量为 $C$，求出航班最多能满足几只奶牛。

一道显而易见的贪心(好像有纯贪心的做法但是还是用的线段树)。

我们设一个数组 $a$ 代表在每个机场时飞机剩余的容量，那么对于任意一群牛的要求 $(s,t,m)$ ($s$ 为起点，$t$ 为终点，$m$ 为这群牛的数量)，我们只用在 $a[s]\sim a[t-1]$ 之间和 $m$ 取次最小值，得到的就是能搭乘的最多牛，减掉就是剩下的容量，同时统计答案。一开始 $a$ 数组初始化为 $C$。

区间求最小值和更新，线段树来一发。

然后剩下的就是处理各种牛的要求了，由于贪心策略，我们把要求 $(s,t,m)$ 按照 $t$ 从小到大排序即可。注意的是我们线段树维护的是什么，在每一个要求 $(s,t,m)$ 中，我们取得是 $a[s]\sim a[t-1]$ 的最小值，所以我们可以一开始就把 $t$ 减掉 $1$，改成求 $a[s]\sim a[t]$ 的最小值。还有一个要点就是由于是往返飞，所以可能 $s>t$。为了使线段树中 $s$ 一直小于 $t$，我们把 $n$ 开两倍，对于这种 $s>t$ 的情况，令 $s=2n-s,t=2n-t-1$ 即可。

注意点：$n$ 开大了 $2$ 倍，线段树也要开打 $2$ 倍；同时可以省略 $a$ 数组，直接求即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define INF 1e9
using namespace std;
const int maxn=1e4+101,maxk=5e4+101;
int n,k,c,ans;
int minn[maxn<<4],add[maxn<<4];
struct cow
{
	int s;
	int t;
	int m;
}a[maxk];
int cmp(cow a,cow b)
{
	if(a.t!=b.t)
		return a.t<b.t;
	return a.s>b.s;
}
void pushup(int rt)
{
	minn[rt]=min(minn[rt<<1],minn[rt<<1|1]);
}
void pushdown(int rt)
{
	if(add[rt]!=0)
	{
		minn[rt<<1]+=add[rt];
		minn[rt<<1|1]+=add[rt];
		add[rt<<1]+=add[rt];
		add[rt<<1|1]+=add[rt];
		add[rt]=0;
		return ;
	}
}
void build(int l,int r,int rt)
{
	add[rt]=0;
	minn[rt]=c;
	if(l==r)
		return ;
	int mid=(l+r)>>1;
	build(lson);
	build(rson);
	pushup(rt);
}
void update(int L,int R,int val,int l,int r,int rt)
{
	if(L<=l&&r<=R)
	{
		minn[rt]+=val;
		add[rt]+=val;
		return ;
	}
	int mid=(l+r)>>1;
	pushdown(rt);
	if(L<=mid)
		update(L,R,val,lson);
	if(R>mid)
		update(L,R,val,rson);
	pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
	if(L<=l&&r<=R)
		return minn[rt];
	int ans=INF;
	int mid=(l+r)>>1;
	pushdown(rt);
	if(L<=mid)
		ans=min(ans,query(L,R,lson));
	if(R>mid)
		ans=min(ans,query(L,R,rson));
	return ans;
}
int main()
{
	scanf("%d%d%d",&k,&n,&c);
	n<<=1;
	for(int i=1;i<=k;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		if(x<y)
		{
			a[i].s=x;
			a[i].t=y-1;
			a[i].m=z;
		}
		else
		{
			a[i].s=n-x;
			a[i].t=n-y-1;
			a[i].m=z;
		}
	}
	sort(a+1,a+k+1,cmp);
	build(1,n,1);
	for(int i=1;i<=k;i++)
	{
		int num=min(a[i].m,query(a[i].s,a[i].t,1,n,1));
		update(a[i].s,a[i].t,-num,1,n,1);
		ans+=num;
	}
	printf("%d",ans);
	return 0;
}