小白样例没过,求大佬差错:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int n,m,ans,f[N],mn[N<<2],lt[N<<2];
struct Cow{
int l,r;
bool operator < (const Cow &rhs) const{
return l==rhs.l?r<rhs.r:l<rhs.l;
}
}c[N];
int ls(int u){return u<<1;}
int rs(int u){return u<<1|1;}
void push_up(int u){mn[u]=min(mn[ls(u)],mn[rs(u)]);}
void push_down(int l,int r,int u){
mn[ls(u)]+=lt[u],mn[rs(u)]+=lt[u],lt[ls(u)]+=lt[u],lt[rs(u)]+=lt[u],lt[u]=0;
}
void build(int l,int r,int u){
if(l==r){mn[u]=f[l];return;}
int mid=l+r>>1;
build(l,mid,ls(u));build(mid+1,r,rs(u));
push_up(u);
}
void up_date(int L,int R,int l,int r,int u){
if(l>=L&&r<=R){mn[u]--,lt[u]--;return;}
int mid=l+r>>1;
push_down(l,r,u);
if(mid>=L)up_date(L,R,l,mid,ls(u));
if(mid<R)up_date(L,R,mid+1,r,rs(u));
push_up(u);
}
int interval_min(int L,int R,int l,int r,int u){
if(l>=L&&r<=R)return mn[u];
int mid=l+r>>1,_mn=-1u/2;
if(mid>=L)_mn=min(_mn,interval_min(L,R,l,mid,ls(u)));
if(mid<R)_mn=min(_mn,interval_min(L,R,mid+1,r,rs(u)));
return _mn;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%d",&f[i]);
for(int i=1;i<=m;i++)scanf("%d%d",&c[i].l,&c[i].r);
sort(c+1,c+m+1);build(1,n,1);
for(int i=1;i<=m;i++)
if(interval_min(1,n,c[i].l,c[i].r,1))ans++,up_date(1,n,c[i].l,c[i].r,1);
cout<<ans<<endl;return 0;
}