[文章目录]
Description
给你n段区间，并给你所有位置上最多能被覆盖区间的个数。询问最多能覆盖多少段区间。
n<=10^5 l,r<=10^5 被覆盖个数<=10^5
贪心
对于所有区间按照r由小到大排序，r相同的按照长度由小到大排序，然后顺次判断是否合法，如果合法则选用，线段树维护一下即可。
证明：对于当前区间i，所影响的区间满足lj<=ri，rj>=ri，它们之间互相也影响，不会出现去掉当前可以满足另外两个未选区间的情况。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000
int n,m,ans,mi[N<<2],lz[N<<2];
struct node
{
int l,r;
}a[N];
bool cmp(node x,node y)
{
return x.r==y.r ? x.r-x.l < y.r-y.l : x.r<y.r;
}
inline int Min(int x,int y){return x<y ? x:y;}
inline void pushup(int pos)
{
mi[pos]=Min(mi[pos<<1],mi[pos<<1|1]);
}
inline void pushdown(int pos)
{
if(lz[pos])
{
mi[pos<<1]+=lz[pos];
mi[pos<<1|1]+=lz[pos];
lz[pos<<1]+=lz[pos];
lz[pos<<1|1]+=lz[pos];
lz[pos]=0;
}
}
void build(int pos,int l,int r)
{
if(l==r)
{
scanf("%d",mi+pos);
return ;
}
int mid=(l+r)>>1;
build(pos<<1,l,mid);
build(pos<<1|1,mid+1,r);
mi[pos]=Min(mi[pos<<1],mi[pos<<1|1]);
}
int query(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r) return mi[pos];
int mid=(l+r)>>1; pushdown(pos);
if(y<=mid) return query(pos<<1,l,mid,x,y);
else if(x>mid) return query(pos<<1|1,mid+1,r,x,y);
else return Min(query(pos<<1,l,mid,x,y),query(pos<<1|1,mid+1,r,x,y));
}
void fix(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r)
{
mi[pos]--; lz[pos]--;
return ;
}
int mid=(l+r)>>1; pushdown(pos);
if(y<=mid) fix(pos<<1,l,mid,x,y);
else if(x>mid) fix(pos<<1|1,mid+1,r,x,y);
else fix(pos<<1,l,mid,x,y),fix(pos<<1|1,mid+1,r,x,y);
pushup(pos);
}
int main()
{
scanf("%d%d",&n,&m); build(1,1,n);
for(int i=1;i<=m;++i) scanf("%d%d",&a[i].l,&a[i].r);
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;++i)
if(query(1,1,n,a[i].l,a[i].r))
ans++,fix(1,1,n,a[i].l,a[i].r);
printf("%d",ans);
return 0;
}