BZOJ_1828_[Usaco2010 Mar]balloc 农场分配_线段树
Description
Input
第1行：两个用空格隔开的整数：N和M * 第2行到N+1行：第i+1行表示一个整数C_i * 第N+2到N+M+1行： 第i+N+1行表示2个整数 A_i和B_i
Output
* 第一行： 一个整数表示最多能够被满足的要求数
Sample Input
5 4
1
3
2
1
3
1 3
2 5
2 3
4 5
1
3
2
1
3
1 3
2 5
2 3
4 5
Sample Output
3
分析：把每头牛按右端点升序排序，然后能插就插，我们需要维护一下这段区间剩余空间的最小值，如果最小值大于0说明能放进去。
这个我们用线段树来维护。
贪心的证明则比较麻烦，我们需要考虑两个右端点不同的线段的几种可能的覆盖情况。
能够发现一个事情，就是右端点小的那个 要么 能更好的利用所需的区间，要么 ｛右端点小的放不进去则右端点大的那个也放不进去。}
所以我们不妨让右端点小的那个先试试。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 100050
#define ls p<<1
#define rs p<<1|1
int t[N<<2],n,m,add[N<<2];
struct C{
int l,r;
}a[N];
bool cmp(const C &x,const C &y){if(x.r==y.r)return x.l>y.l;return x.r<y.r; }
void build(int l,int r,int p)
{
if(l==r){
scanf("%d",&t[p]);
return ;
}
int mid=l+r>>1;
build(l,mid,ls);build(mid+1,r,rs);
t[p]=min(t[ls],t[rs]);
}
void pushdown(int p)
{
int d=add[p];
if(d)
{
t[ls]+=d;add[ls]+=d;
t[rs]+=d;add[rs]+=d;
add[p]=0;
}
}
void update(int l,int r,int x,int y,int c,int p)
{
if(x<=l&&y>=r){
t[p]+=c;
add[p]+=c;
return;
}
int mid=l+r>>1;
pushdown(p);
if(x<=mid) update(l,mid,x,y,c,ls);
if(y>mid) update(mid+1,r,x,y,c,rs);
t[p]=min(t[ls],t[rs]);
}
int query(int l,int r,int x,int y,int p)
{
if(x<=l&&y>=r) return t[p];
int re=1<<30;
pushdown(p);
int mid=l+r>>1;
if(x<=mid) re=min(re,query(l,mid,x,y,ls));
if(y>mid) re=min(re,query(mid+1,r,x,y,rs));
t[p]=min(t[ls],t[rs]);
return re;
}
int main()
{
scanf("%d%d",&n,&m);
int i;
memset(t,0x3f,sizeof(t));
build(1,n,1);
for(i=1;i<=m;i++) scanf("%d%d",&a[i].l,&a[i].r);
sort(a+1,a+m+1,cmp);
int ans=0;
for(i=1;i<=m;i++)
{
int tmp=query(1,n,a[i].l,a[i].r,1);
if(tmp>0){
ans++;
update(1,n,a[i].l,a[i].r,-1,1);
}
}
printf("%d\n",ans);
}