[USACO10MAR]仓配置Barn Allocation
思路：
贪心+线段树维护；
代码：
#include <bits/stdc++.h> using namespace std; #define maxn 100005 #define INF 0x3f3f3f3f #define maxtree maxn<<2 struct QueryType { int l,r; bool operator<(const QueryType pos)const { if(pos.r==r) return l<pos.l; return r<pos.r; } }; struct QueryType qu[maxn]; int n,m,ai[maxn],L[maxtree],R[maxtree],mid[maxtree],val[maxtree],tag[maxtree]; inline void in(int &now) { char Cget=getchar();now=0; while(Cget>'9'||Cget<'0')Cget=getchar(); while(Cget>='0'&&Cget<='9') { now=now*10+Cget-'0'; Cget=getchar(); } } void build(int now,int l,int r) { L[now]=l,R[now]=r; if(l==r) { val[now]=ai[l]; return ; } mid[now]=l+r>>1; build(now<<1,l,mid[now]); build(now<<1|1,mid[now]+1,r); val[now]=min(val[now<<1],val[now<<1|1]); } void pushdown(int now) { val[now<<1]+=tag[now],tag[now<<1]+=tag[now]; val[now<<1|1]+=tag[now],tag[now<<1|1]+=tag[now]; tag[now]=0; } void updata(int now,int l,int r) { if(L[now]>=l&&R[now]<=r) { val[now]--,tag[now]--; return; } if(tag[now]!=0) pushdown(now); if(l<=mid[now]) updata(now<<1,l,r); if(r>mid[now]) updata(now<<1|1,l,r); val[now]=min(val[now<<1],val[now<<1|1]); } int query(int now,int l,int r) { if(L[now]>=l&&R[now]<=r) return val[now]; if(tag[now]!=0) pushdown(now);int res=INF; if(l<=mid[now]) res=min(res,query(now<<1,l,r)); if(r>mid[now]) res=min(res,query(now<<1|1,l,r)); return res; } int main() { in(n),in(m); for(int i=1;i<=n;i++) in(ai[i]); for(int i=1;i<=m;i++) in(qu[i].l),in(qu[i].r); sort(qu+1,qu+m+1),build(1,1,n);int ans=0; for(int i=1;i<=m;i++) { if(query(1,qu[i].l,qu[i].r)) ans++,updata(1,qu[i].l,qu[i].r); } cout<<ans; return 0; }