2025_5_4 T3

· · 题解

以前kaka讲过这道题目，但当时的做法放在这道题目上有些极限，需要特判大数据，所以我们的做法是排序

好题，整体难度中位蓝，放CFdiv2 E完全合理

首先，因为线段是求交，所以最多只会有一个组中的线段是空的，因为我们可以把无用的线段都放到一个集合里，显然，此时可以分出两种情况

f1,有集合为空

显然，我们把所有的线按r-l为关键字降序排列，取前k-1大，每条单独一组，剩下n-k+1条为一组即可

bool cmp1(MADELINE x,MADELINE y) {return x.r-x.l>y.r-y.l;}

void f1()
{
  int mi=inf,ma=0;
  sort(line+1,line+n+1,cmp1);
  for(int i=1;i<=k-1;i++) ans+=line[i].r-line[i].l;
  for(int i=k;i<=n;i++) mi=min(mi,line[i].r),ma=max(ma,line[i].l);
  ans+=max(mi-ma,0);
}

f2,无集合为空

这是更为复杂的情况

为了方便解题，我们把线段们按r为关键字升序排列

注意到，当线段A包含线段B时，A要么单开一组，要么和B在同一组，只有这样才可使策略最优，所以，我们先把形如A的全部抛开，故情况如下

讨论B

此时发现，去掉形如A的线段后，l与r都是升序

我们把图中的线从上往下依次命名为1, 2 , 3

显然，线段整体的交为r_1-l_3，（代码实现不用和0取\max),最终发现，想要最大化答案，其实本质是把线段们连续的分成很多组，每组的线段编号由[x,y]组成，贡献为r_x-l_y

例如上图可以化为两组:[1,1],[2,3]，贡献即为(r_1-l_1)+(r_2-l_3)

假设m为B的总线段数

立马联想到，初始分组为[1,m]，贡献r_1-l_m，我们假设在其中增加t个断点，把它们分为了[1,c1],[c_1+1,c_2],[c_2+1,c_3]......[c_t+1,m]

总贡献由r_1-l_m变为

(c_0=1,c_{t+1}=m) \sum_{i=1}^{t+1}r_{c_{i-1}}-l_{c_i}

本质的，增加一个断点p，其实只会增加r_{p+1}-l_p的贡献，假设我们加t个断点，直接取前t大的r_{p+1}-l_p即可

讨论A

解决完形如B的家伙后，我们再想想A

因为A的处理方法只有两种，要么单开，要么跟着对应的B，针对前者，贡献自然是r-l，对于后者，因为所属的B被A完全包含，所以A的贡献是完全没有的，故为0

假设取了t个断点，取剩下的k-t-1大的r-l，和前者的贡献加上就行（因为t个断点是t+1组，故为n-t-1）

所以，我们枚举t，把贡献算出来，取\max就能解决问题了

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10,inf=0x3f3f3f3f;
int n,k,cnt1,cnt2;
int c[maxn];
ll ans;
struct MADELINE{//模拟赛题目背景主角（玛德不如回去爬山)
    int l,r;
}line[maxn],line1[maxn],line2[maxn];
bool cmp(int x,int y) {return x>y;}
bool cmp1(MADELINE x,MADELINE y) {return x.r-x.l>y.r-y.l;}
bool cmp2(MADELINE x,MADELINE y) {return x.r!=y.r?x.r<y.r:x.l>y.l;}
int read()
{
    int ret=0,w=1;char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
    return ret*w;
}
void inpu()
{
    n=read(),k=read();
    for(int i=1;i<=n;i++) line[i].l=read(),line[i].r=read();
}
void pre()
{
    int mi=inf,ma=0;
    sort(line+1,line+n+1,cmp1);
    for(int i=1;i<=k-1;i++) ans+=line[i].r-line[i].l;
    for(int i=k;i<=n;i++) mi=min(mi,line[i].r),ma=max(ma,line[i].l);
    ans+=max(mi-ma,0);
}//一个集合为空
void deal()
{//没有集合为空
    int ma=-1;ll sum1=0,sum2=0;//sum1是A的贡献，sum2是B的的贡献
    sort(line+1,line+n+1,cmp2);
    for(int i=1;i<=n;i++)
    {
        if(line[i].l<=ma) line1[++cnt1]=line[i];//形如A的线段
        else
        {
            ma=line[i].l;
            line2[++cnt2]=line[i];//形如B的线段
        }
    }
    sum2=line2[1].r-line2[cnt2].l;
    for(int i=1;i<cnt2;i++) c[i]=line2[i+1].r-line2[i].l;//提前算出断点的贡献
    cnt2--;
    sort(line1+1,line1+cnt1+1,cmp1);sort(c+1,c+cnt2+1,cmp);
    if(cnt1>=k-1)//因为cnt1可能比k小，所以有两种情况，防止k太大，整出一些不存在的贡献
    {
        for(int i=1;i<k;i++) sum1+=line1[i].r-line1[i].l;
        ans=max(ans,sum1);
        for(int i=1;i<k;i++)
        {
            sum1-=line1[k-i].r-line1[k-i].l,sum2+=c[i];
            ans=max(ans,sum1+sum2);
        }
    }else
    {
        for(int i=1;i<=cnt1;i++) sum1+=line1[i].r-line1[i].l;
        for(int i=1;i<=k-cnt1-1;i++) sum2+=c[i];
        ans=max(ans,max(sum1,sum1+sum2));
        for(int i=1;i<=cnt1;i++)
        {
            if(k-cnt1-1+i<0) break;
            sum1-=line1[cnt1-i+1].r-line1[cnt1-i+1].l,sum2+=c[k-cnt1-1+i];
            ans=max(ans,sum1+sum2);
        }
    }
}
void solve()
{
    inpu();
    pre();
    deal();
    printf("%lld",ans);
}
signed main()
{
    int t=1;
    while(t--) solve();
    return 0;
}

我总感觉代码怪怪的，但确实能过

你就别管吧，过了就好