洛谷1712 [NOI2016]区间

题意

有 $n(\le 5\times 10^5)$ 个区间，要从中选出 $m(\le 2\times 10^5)$ 个区间，要求存在一个点被覆盖了 $m$ 次，求最大区间长度与最小区间长度差值 的最小值。

题解

贪心，将所有区间按长度从小到大排序，答案一定是一段连续的区间。所以可以用线段树维护覆盖的次数，然后尺取法不断取被覆盖次数最大为 $m$ 的一段并更新答案。

需要离散化预处理。需要注意区间长度是原来区间的长度而不是离散化后的区间长度。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=500005;
struct Tree {
    int left,right,mx,delta;
} tree[N<<3];
struct node {
    int s,id,len;
} s[N<<1];
struct node2 {
    int l,r,len;
} x[N];
int n,m;

inline bool cmp1(node x,node y) { return x.s<y.s; }

inline bool cmp2(node2 x,node2 y) { return x.len<y.len; }

inline void pushup(int x) { tree[x].mx=max(tree[x<<1].mx,tree[x<<1|1].mx); }

inline void pushdown(int x)
{
    tree[x<<1].mx+=tree[x].delta;
    tree[x<<1|1].mx+=tree[x].delta;
    tree[x<<1].delta+=tree[x].delta;
    tree[x<<1|1].delta+=tree[x].delta;
    tree[x].delta=0;
}

void build(int x,int l,int r)
{
    tree[x].left=l;
    tree[x].right=r;
    if (r-l>1)
    {
        int mid=(l+r)>>1;
        build(x<<1,l,mid);
        build(x<<1|1,mid,r);
    }
}

void add(int x,int l,int r,int delta)
{
    if (l<=tree[x].left && r>=tree[x].right)
    {
        tree[x].mx+=delta;
        tree[x].delta+=delta;
    }
    else
    {
        if (tree[x].delta) pushdown(x);
        int mid=(tree[x].left+tree[x].right)>>1;
        if (l<mid) add(x<<1,l,r,delta);
        if (r>mid) add(x<<1|1,l,r,delta);
        pushup(x);
    }
}

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++)
    {
        s[(i<<1)-1].s=read();
        s[i<<1].s=read();
        s[(i<<1)-1].id=s[i<<1].id=i;
        s[(i<<1)-1].len=s[i<<1].len=s[i<<1].s-s[(i<<1)-1].s;
    }
    n<<=1;
    sort(s+1,s+n+1,cmp1);
    int cnt=0;
    s[0].s=-1;
    for (int i=1;i<=n;i++)
    {
        if (s[i].s!=s[i-1].s) cnt++;
        if (!x[s[i].id].l) x[s[i].id].l=cnt;
        else x[s[i].id].r=cnt,x[s[i].id].len=s[i].len; //离散化
    }
    n>>=1;
    sort(x+1,x+n+1,cmp2); //按长度排序
    build(1,1,cnt+1);
    int ans=1e9;
    for (int l=0,r=0;l<=n;)
    {
        for (;r<=n && tree[1].mx<m;r++,add(1,x[r].l,x[r].r+1,1));
        if (r>n) break;
        for (;l<r && tree[1].mx>=m;l++,add(1,x[l].l,x[l].r+1,-1));
        ans=min(ans,x[r].len-x[l].len);
    }
    if (ans==1e9) return 0&puts("-1");
    return !printf("%d",ans);
}