文章目录

题目链接：

https://ac.nowcoder.com/acm/contest/297#question

C-little w and Segment Coverage

题意：给M个区间，把每个区间上的点都加1，然后问删除哪一个点后不会被覆盖的点最少
我觉得这道题挺好的，就适合我们这些小白做，看题解能够收获很多~
哇，线段树原来还阔以统计区间内小于等于某个数x的个数有多少个呀，我太挫了，这个竟然没想到，经宋大佬指导后理解了，只要这段区间内的最小值都小于x的话，那么这段区间不就是个数了蛮

然后删除这段区间，那么这段区间的每个值不就都会减少1嘛，所以能覆盖的点其实就是值大于等于2的点，所以直接找大于等于2的点的个数就行了

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
int N,M;
int Min[maxn<<2],a[maxn];
void pushup(int id)
{
	Min[id]=min(Min[id<<1],Min[id<<1|1]);
}
void Build(int id,int L,int R)
{
	Min[id]=1e9;
	if(L==R)Min[id]=a[L]; 
	else
	{
		int mid=L+R>>1;
		Build(id<<1,L,mid);
		Build(id<<1|1,mid+1,R);
		pushup(id);
	}
}
int query(int id,int L,int R,int qL,int qR,int val)//求[qL,qR]内大于等于val的有多少个 
{
	if(L==R)
	{
		if(Min[id]>=val)return 1;
		else return 0;
	}
	if(qL<=L&&qR>=R && Min[id]>=val)return(R-L+1);
	else
	{
		int mid=L+R>>1;
		int res=0;
		if(qL<=mid)res+=query(id<<1,L,mid,qL,qR,val);
		if(qR>=mid+1)res+=query(id<<1|1,mid+1,R,qL,qR,val);
		return res;
	}
}
int L[maxn],R[maxn];
int main()
{
	while(cin>>N>>M)
	{
		memset(a,0,sizeof a);
		for(int i=1;i<=M;i++)
		{
			scanf("%d%d",L+i,R+i);
			a[L[i]]++,a[R[i]+1]--;
		}
		int cnt=0;
		for(int i=1;i<=N;i++)
		{
			a[i]+=a[i-1];
			if(a[i]==0)cnt++;
		}
		Build(1,1,N);
		int ans=0;
		int MIN=N,pos=-1;//MIN表示删除一条边最少会增加多少个点不能被覆盖 
		for(int i=1;i<=M;i++)
		{
			int l=L[i],r=R[i];
			int ans=r-l+1-query(1,1,N,l,r,2);
			if(ans<=MIN)
			{
				MIN=ans;
				pos=i;
			}
		}
		cout<<pos<<" "<<cnt+MIN<<endl;
	}
}

官方题解

官方题解没有用线段树，而是直接找值为1的数，然后看区间内值为1的数有多少个，如果删去这条边，那么值为1的就变成0了，那这些点就肯定不会被覆盖到了，就是这样统计的

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
int N,M;
int a[maxn],sum[maxn],L[maxn],R[maxn];
int main()
{
	while(cin>>N>>M)
	{
		memset(a,0,sizeof a);
		memset(sum,0,sizeof sum);
		for(int i=1;i<=M;i++)
		{
			scanf("%d%d",L+i,R+i);
			a[L[i]]++,a[R[i]+1]--;
		}
		int cnt=0;
		for(int i=1;i<=N;i++)
		{
			a[i]+=a[i-1];
			if(a[i]==0)cnt++;
			if(a[i]==1)sum[i]=1;
			sum[i]+=sum[i-1];
		}
		int MIN=N,pos=-1;
		for(int i=1;i<=M;i++)
		{
			int l=L[i],r=R[i];
			int ans=sum[r]-sum[l-1];
			if(ans<=MIN)
			{
				MIN=ans;
				pos=i;
			}
		}
		cout<<pos<<" "<<cnt+MIN<<endl;
	}
}