P1712 题解

__vector__ · 2022-06-10 19:43:15 · 个人记录

思路

选择的 m 个区间的花费是其中最长的区间减去最短区间，那么，为了使花费最小，这 m 个区间在长度排名上是要连续的。
所以先对这 n 个区间排序，然后枚举每一个要选的区间。每枚举一个区间，都将区间中每一个点覆盖次数加一，然后判断是否有一个点的覆盖次数超过了 m 次，那么就开始更新答案，具体细节：

1. 删除最先加入且还没被删的区间
2. 更新答案
3. 如果仍然有一个点的覆盖次数超过了 m 次，go to step 1

至于区间覆盖次数记录，使用线段树记录即可，另外注意要离散化。

另注：
如果到最终也没有更新答案，那么无解

代码：

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    const int maxn=5e5+5;
    //---------IO----------
    int n,m;
    struct Section
    {
        int l,r,len;
        bool operator <(const Section& b)
        {
            return len<b.len;
        }
    }sec[maxn<<3];
    int cnt;
    int all[maxn<<3];
    //------Trie--------
    struct Trie
    {
        int max,lazy;
    }trie[maxn<<3];
    inline void push_down(int node)
    {
        if(trie[node].lazy==0)return;
        trie[node<<1].lazy+=trie[node].lazy;
        trie[node<<1].max+=trie[node].lazy;
        trie[node<<1|1].lazy+=trie[node].lazy;
        trie[node<<1|1].max+=trie[node].lazy;
        trie[node].lazy=0;
    }
    inline void push_up(int node)
    {
        trie[node].max=max(trie[node<<1].max,trie[node<<1|1].max);
    }
    void Modify(int node,int _l,int _r,int l,int r,int val)
    {
        if(_r<l||_l>r)
        {
            return;
        }
        if(_l>=l&&_r<=r)
        {
            trie[node].lazy+=val;
            trie[node].max+=val;
            return;
        }
        push_down(node);
        int mid=(_l+_r)>>1;
        if(l<=mid)Modify(node<<1,_l,mid,l,r,val);
        if(r>mid)Modify(node<<1|1,mid+1,_r,l,r,val);
        push_up(node);
    }
    void main()
    {
        scanf("%d%d",&n,&m);
        int li,ri;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&li,&ri);
            all[++cnt]=li;
            all[++cnt]=ri;
            sec[i].l=li;
            sec[i].r=ri;
            sec[i].len=sec[i].r-sec[i].l;
        }
        sort(all+1,all+cnt+1);
        cnt=unique(all+1,all+cnt+1)-all-1;
        for(int i=1;i<=n;i++)
        {
            sec[i].l=lower_bound(all+1,all+cnt+1,sec[i].l)-all;
            sec[i].r=lower_bound(all+1,all+cnt+1,sec[i].r)-all;
        }
        sort(sec+1,sec+n+1);
        int fir=1;
        int ans=0x3f3f3f3f;
        for(int i=1;i<=n;i++)
        {
            Modify(1,1,cnt,sec[i].l,sec[i].r,1);
            while(trie[1].max>=m)
            {
                ans=min(ans,sec[i].len-sec[fir].len);
                Modify(1,1,cnt,sec[fir].l,sec[fir].r,-1);
                fir++;
            }
        }
        if(ans==0x3f3f3f3f)
        {
            printf("-1");
        }
        else
        {
            printf("%d",ans);
        }
    }
}
int main()
{
    Main::main();
    return 0;
}