【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1828
【题目大意】
现在有一些线段[l,r]的需求需要满足，i位置最多允许a[i]条线段堆叠,
问最多能满足多少条线段的需求
【题解】
我们将所有的线段按照右端点排序，那么从头到尾考虑能不能满足需求一定能得到最优解，
因为对于相同右端点的来说，先后顺序不影响放入，
而对于右端点不同的来说，右端点靠前的先处理一定比靠后的先处理更优。
处理方式相当于线段树的区间查询和区间修改。
【代码】
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100010;
const int INF=0x3f3f3f3f;
struct data{int l,r;}p[N];
bool cmp(data a,data b){return a.r<b.r;}
int tag[N<<2],T[N<<2],a[N];
void up(int x){T[x]=min(T[x<<1],T[x<<1|1]);}
void pd(int x){
if(tag[x]){
T[x<<1]+=tag[x]; T[x<<1|1]+=tag[x];
tag[x<<1]+=tag[x]; tag[x<<1|1]+=tag[x];
tag[x]=0;
}
}
void build(int x,int l,int r){
int mid=(l+r)>>1;
if(l==r){T[x]=a[l];tag[x]=0;return;}
build(x<<1,l,mid); build(x<<1|1,mid+1,r);
up(x);
}
void update(int x,int l,int r,int L,int R,int p){
int mid=(l+r)>>1;
if(L<=l&&r<=R){T[x]+=p;tag[x]+=p;return;} pd(x);
if(L<=mid)update(x<<1,l,mid,L,R,p);
if(R>mid)update(x<<1|1,mid+1,r,L,R,p);
up(x);
}
int query(int x,int l,int r,int L,int R){
int mid=(l+r)>>1;
//printf("%d %d %d
",l,r,T[x]);
if(L<=l&&r<=R)return T[x]; pd(x);
int res=INF;
if(L<=mid)res=min(res,query(x<<1,l,mid,L,R));
if(R>mid)res=min(res,query(x<<1|1,mid+1,r,L,R));
return res;
}
int n,m;
int main(){
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
build(1,1,n);
for(int i=1;i<=m;i++)scanf("%d%d",&p[i].l,&p[i].r);
sort(p+1,p+m+1,cmp);
int ans=0;
for(int i=1;i<=m;i++){
int x=query(1,1,n,p[i].l,p[i].r);
//printf("%d %d
",p[i].l,p[i].r);
//printf("%d
",x);
if(x){
ans++;
update(1,1,n,p[i].l,p[i].r,-1);
}
}printf("%d
",ans);
}return 0;
}