蒟蒻求助
查看原帖
蒟蒻求助
115668
y0y68楼主2020/7/9 19:01

小白样例没过,求大佬差错:

#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;
}
2020/7/9 19:01
加载中...