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左右