题目：Barn Allocation
思路：
贪心+线段树。
先把所有牛的序求按右端点从小到大，左端点从大到小排序。然后顺次的对于每一头牛，如果它的需求可以被满足，ans++，否则跳过。
比如样例排序后可得：
| 1 | 3 | 2 | 1 | 3 | 容纳空间
| 1 | 2 | 3 | 4 | 5 | 畜栏号
XX XX XX Cow3
XX XX XX XX XX Cow1
XX XX XX Cow4
XX XX XX XX XX XX Cow2
选择3,1,4这三头牛是最优解。
为什么这样是成立的呢？
假设选到第i头牛时不成立，并且它和前面的某头牛j有这样的位置关系：
| 1 | 2 | 3 | 畜栏号
XX XX XX XX 某头牛j
XX XX XX 第i头牛
这是可以看出，一定是区域2发生了冲突。由于之前的排序规则，区域1的牛不会对j产生影响，而2、3会。所以删掉j仅会影响区域2，而删掉i会影响2、3。所以删掉i更优。
当然两头牛的位置关系还有几种，道理类似。
如何判断需求是否被满足？
每添加一头牛，可以看做它的需求区间内的牛栏容量每一个减1，那么这个区间问题就可以用线段树优化了。
对于畜栏的容量建立一颗线段树。在处理每一头牛时，先查询这头牛所对应的区间[l,r]是否每一个值都大于等于1，如果满足条件，说明这头牛可用，那么就对[l,r]整体减1。
代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <cstring>
#include <map>
using namespace std;#define maxn 100000
#define inf (1<<30)struct Pair {int x,y;bool operator < (const Pair& oth) const {return y<oth.y||(y==oth.y&&x>oth.x);}
};int n,m;
int c[maxn+5];
Pair cw[maxn+5];int a[maxn*4+5];
int lzy[maxn*4+5]={0};int p,q;
int ans=0;void make_tree(int o,int l,int r) {if(l==r) {a[o]=c[l];return ;}int lc=o*2,rc=o*2+1,mid=l+(r-l)/2;make_tree(lc,l,mid),make_tree(rc,mid+1,r);a[o]=min(a[lc],a[rc]);
}void pushdown(int o,int lc,int rc){lzy[lc]+=lzy[o],lzy[rc]+=lzy[o];a[lc]+=lzy[o],a[rc]+=lzy[o];lzy[o]=0;
}int query(int o,int l,int r) {if(p<=l&&q>=r) return a[o];if(p>r||q<l) return inf;int lc=o*2,rc=o*2+1,mid=l+(r-l)/2;pushdown(o,lc,rc);return min(query(lc,l,mid),query(rc,mid+1,r));
}void update(int o,int l,int r) {if(p<=l&&q>=r) {a[o]--,lzy[o]--;return ;}if(p>r||q<l) return ;int lc=o*2,rc=o*2+1,mid=l+(r-l)/2;pushdown(o,lc,rc);update(lc,l,mid),update(rc,mid+1,r);a[o]=min(a[lc],a[rc]);
}int main() {scanf("%d%d",&n,&m);for(int i=1; i<=n; i++) scanf("%d",&c[i]);make_tree(1,1,n);for(int i=1; i<=m; i++) scanf("%d%d",&cw[i].x,&cw[i].y);sort(cw+1,cw+m+1);for(int i=1; i<=m; i++) {p=cw[i].x,q=cw[i].y;if(query(1,1,n)>0) {ans++;update(1,1,n);}}printf("%d\n",ans);return 0;
}