题目描述
此题可以根据区间合并模板进行适当改进
主要是在区间合并或者更新时要给拔树的区间进行标志,可以标志长度,也可以标志性质
我的思路是对于区间合并的情况,让这一区间的值都+1(初始为0),这里涉及到区间的增减问题,考虑使用差分数组控制为O(1)
对于不可合并的情况,直接+1即可
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
typedef pair<int,int>PII;
PII p[N];
int L,M;
int s[10010];//这是差分数组,初始全0也满足差分性质
int main()
{
cin>>L>>M;
for(int i=0;i<M;i++)
{
int l,r;
scanf("%d %d",&l,&r);
p[i]={l,r};
}
sort(p,p+M);
//区间合并部分
int st=-2,ed=-2;
for(int i=0;i<M;i++)
if(p[i].first<=ed+1)
{
ed=max(ed,p[i].second);
ed=min(ed,L);
s[st]+=1,s[ed+1]-=1;//转换为查分数组的两点赋值
}
else
{
st=p[i].first,ed=min(p[i].second,L);
s[st]+=1,s[ed+1]-=1;//转换为查分数组的两点赋值
}
//重新获得用于标记的数组,可能有的点被重复+1过,没关系,只要没加过的区间
for(int i=1;i<=L;i++)
s[i]+=s[i-1];
int res=0;
for(int i=0;i<=L;i++)
if(!s[i]) res++;
cout<<res<<endl;
return 0;
}