CF930C Solution

题目链接

题解

设\(a_i\)表示节点\(i\)被覆盖次数，用差分求出。可以发现，如果存在节点\(i\)使得\(a_{i-1}>a_i,a_{i+1}>a_i\)则一定不存在被所有线段覆盖的节点（\(i\)一定会把两边的线段断开），因此最长单峰子序列（先单调不降后单调不升）的长度即为答案。正反2次求LIS，记录\(l_i,r_i\)表示\([1,i]\)的最长不降子序列长度与\([i,n]\)的最长不升子序列长度，枚举峰值即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int l[N],r[N],cha[N],st[N],top;//cha:上文中的a
int main()
{
	int n,m,ans=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) 
	{
		scanf("%d%d",&l[i],&r[i]);
		cha[l[i]]++,cha[r[i]+1]--;
	}
	for(int i=1;i<=m;i++) cha[i]+=cha[i-1];
	for(int i=1;i<=m;i++)
	{
		if(cha[i]>=st[top]) st[++top]=cha[i];
		else
		{
			int pos=upper_bound(st+1,st+top+1,cha[i])-st;
			st[pos]=cha[i];
		}
		l[i]=top;
	}
	top=0;
	for(int i=m;i>=1;i--)
	{
		if(cha[i]>=st[top]) st[++top]=cha[i];
		else
		{
			int pos=upper_bound(st+1,st+top+1,cha[i])-st;
			st[pos]=cha[i];
		}
		r[i]=top;
	}
	for(int i=1;i<=m;i++) ans=max(ans,l[i]+r[i]-1);//cha[i]会被重复计算,因此需-1
	printf("%d",ans);
	return 0;
}