【Luogu1937】仓配置(贪心,线段树)

时间:2023-03-08 19:46:29
【Luogu1937】仓配置(贪心,线段树)

【Luogu1937】仓配置

题面

直接找洛谷把。。。

题解

很明显的贪心吧

按照线段的右端点为第一关键字,左端点第二关键字排序

然后线段树维护区间最小就可以啦

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
using namespace std;
#define MAX 110000
#define lson (now<<1)
#define rson (now<<1|1)
inline int read()
{
int x=0,t=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
int t[MAX<<2];
int ly[MAX<<2];
int N,M,a[MAX];
void pushdown(int now)
{
int lyy=ly[now];
t[lson]-=lyy;t[rson]-=lyy;
ly[lson]+=lyy;ly[rson]+=lyy;
ly[now]=0;
}
void putlazy(int now)
{
t[now]--;ly[now]++;
}
void build(int now,int l,int r)
{
if(l==r){t[now]=a[l];return;}
int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
t[now]=min(t[lson],t[rson]);
}
int Query(int now,int l,int r,int al,int ar)
{
if(l==al&&r==ar)return t[now];
if(ly[now])pushdown(now);
int mid=(l+r)>>1;
if(ar<=mid)return Query(lson,l,mid,al,ar);
else if(al>mid)return Query(rson,mid+1,r,al,ar);
else return min(Query(lson,l,mid,al,mid),Query(rson,mid+1,r,mid+1,ar));
}
void Modify(int now,int l,int r,int al,int ar)
{
if(l==al&&r==ar){putlazy(now);return;}
int mid=(l+r)>>1;
if(ly[now])pushdown(now);
if(ar<=mid)Modify(lson,l,mid,al,ar);
else if(al>mid)Modify(rson,mid+1,r,al,ar);
else {Modify(lson,l,mid,al,mid);Modify(rson,mid+1,r,mid+1,ar);}
t[now]=min(t[lson],t[rson]);
}
struct Link
{
int l,r;
}gg[MAX];
inline bool operator <(Link a,Link b)
{
if(a.r!=b.r)return a.r<b.r;
return a.l>b.r;
}
int main()
{
N=read();M=read();
for(int i=1;i<=N;++i)a[i]=read();
for(int i=1;i<=M;++i)gg[i].l=read(),gg[i].r=read();
sort(&gg[1],&gg[M+1]);
build(1,1,N);
int ans=0;
for(int i=1;i<=M;++i)
{
int dd=Query(1,1,N,gg[i].l,gg[i].r);
if(!dd)continue;
++ans;
Modify(1,1,N,gg[i].l,gg[i].r);
}
cout<<ans<<endl;
return 0;
}