Description

给定 \(n\) 条线段，符合被至少 \(k\) 条线段的点合法，求最少的线段集使得包含所有合法点，并且不包含其他点。

---

Solution

本题正解是 \(\Theta(n\log n)\) 的差分，这里介绍一种常数略大的 \(\Theta(n\log n)\) 做法。

考虑一条线段对于一个点何时做贡献，如图（样例 1）

设当前点为 \(a\)，其右边有 \(y\) 个右端点，\(x\) 个左端点。

右端点在其右边的可能会包含它，但是如果左端点也在它右边就无法覆盖它，两者数量相减即为它被多少个区间包含。

左，右端点比 \(a\) 大即为值比它大，可以用离散化+树状数组做到 \(\Theta(n\log n)\) 维护。

因为一段答案线段必定结束于 \(n\) 条线段中某一条线段的右端点，所以离散化后的答案正确。

如果一个点既处在一条线段的右端点，又存在于一条线段的左端点，此时他是被两条线段包含的，所以统计答案时，右端点的范围为 \([a,cnt]\),左端点的范围为 \([a+1,cnt]\)(\(cnt\)为离散化后的元素个数)。

我们发现当出现上图绿色和蓝色线段中间有 \((2,3)\) 的空缺时，不好直接维护中间的个数，所以我们把离散化后的元素乘 2 再减 1，就可以保证空缺的答案正确，且不会与上一个点以及下一个点一起被记入一条答案线段。

此时新的答案线段的左端点为 5。

Code:

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int n,k,b[4000005],m,cnt;
int vis[4000005],BIT1[4000005],BIT2[4000005],tot=1,Max=-1;
const int INF=0x3f3f3f3f;
int lowbit(int x)
{
	return x&-x;
}
void update1(int x,int k)
{
	for(int i=x;i<=cnt*2-1;i+=lowbit(i))
	{
		BIT1[i]+=k;
	}
}
int Ans1(int x)//统计左节点
{
	int ans=0;
	for(int i=x;i>0;i-=lowbit(i))
	{
		ans+=BIT1[i];
	}
	return ans;
}
void update2(int x,int k)
{
	for(int i=x;i<=cnt*2-1;i+=lowbit(i))
	{
		BIT2[i]+=k;
	}
}
int Ans2(int x)//统计右节点
{
	int ans=0;
	for(int i=x;i>0;i-=lowbit(i))
	{
		ans+=BIT2[i];
	}
	return ans;
}
struct ren{
	int l,r;
}a[4000005],Ans[4000005];
bool cmp(ren x,ren y)
{
	return x.l==y.l?x.r<y.r:x.l<y.l;
}
int main()
{
	memset(vis,-INF,sizeof(vis));
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].l,&a[i].r);
		b[++m]=a[i].l;
		b[++m]=a[i].r;
	}
	sort(a+1,a+1+n,cmp);
	sort(b+1,b+1+m);
	cnt=unique(b+1,b+1+m)-b-1;
	for(int i=1;i<=n;i++)
	{
		int x=lower_bound(b+1,b+1+cnt,a[i].l)-b,y=lower_bound(b+1,b+1+cnt,a[i].r)-b;
		x=x*2-1;
		y=y*2-1;
		vis[x]=a[i].l;
		vis[y]=a[i].r;
		a[i].l=x;
		a[i].r=y;
		Max=max(Max,a[i].r);
		update1(a[i].l,1);
		update2(a[i].r,1);
	}
	for(int i=1;i<=cnt*2-1;i++)
	{
		Ans[i].l=Ans[i].r=-INF;
	}
	for(int i=a[1].l;i<=Max;i++)
	{
		int x=Ans2(cnt*2-1)-Ans2(i-1),y=Ans1(cnt*2-1)-Ans1(i);
		if(x-y>=k&&vis[i]!=-INF)
		{
			if(Ans[tot].l==-INF){
				Ans[tot].l=vis[i];
				Ans[tot].r=vis[i];
				while(Ans2(cnt*2-1)-Ans2(i-1)-Ans1(cnt*2-1)+Ans1(i)>=k&&Max)
				{
					if(vis[i]!=-INF)
					{
						Ans[tot].r=vis[i];
					}
					i++;
				}
				i--;
				tot++;
			}
		}
	}
	tot--;//多加了一次，固减去
	printf("%d\n",tot);
	for(int i=1;i<=tot;i++)
	{
		printf("%d %d\n",Ans[i].l,Ans[i].r);
	}
	return 0;
}//实际上比差分只慢100ms左右