牛客模拟、差分题---校门外的树

校门外的树

模拟写法

• 把在区间的所有都标记一下，没标记的计数
• 这个题数据范围不是很大，可以这样

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e4+2;

int cnt[maxn];
int main(){
  	int l,m;cin>>l>>m;
  	while(m--){
  		int a,b;cin>>a>>b;
  		for(int i=a;i<=b;i++) cnt[i]++;
	}
	int ans=0;
	for(int i=0;i<=l;i++) if(!cnt[i]) ans++;
	cout<<ans<<"
";
    return 0;
}

差分写法

• 适用于数据范围大的
• 差分只用把端点处变化一下，eg：区间里面的树都-1（默认0为有树）
• 最后求原数组，差分前缀和化，把数组上所有的0计数

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e4+2;

int q[maxn],a[maxn];
int main(){
    int l,m,x,y;cin>>l>>m;
    for(int i=1;i<=m;i++){
    	cin>>x>>y;
    	q[x]-=1;
    	q[y+1]+=1;
	}
	int ans=0;
	a[0]=q[0];
	for(int i=1;i<=l;i++) a[i]=a[i-1]+q[i];
	for(int i=0;i<=l;i++){
		if(!a[i]) ans++;
	}
	cout<<ans<<"
";
    return 0;
}