[NOI2016]区间题解(决策单调性+线段树优化)

4653: [Noi2016]区间

Time Limit: 60 Sec Memory Limit: 256 MB
Submit: 1593 Solved: 869
[Submit][Status][Discuss]

Description

在数轴上有 n个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间，使得这 m个区间共同包含至少一个位置。换句话说，就是使得存在一个 x，使得对于每一个被选中的区间 [li,ri]，都有 li≤x≤ri。

对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li，即等于它的右端点的值减去左端点的值。

求所有合法方案中最小的花费。如果不存在合法的方案，输出 −1。

Input

第一行包含两个正整数 n,m用空格隔开，意义如上文所述。保证 1≤m≤n

接下来 n行，每行表示一个区间，包含用空格隔开的两个整数 li 和 ri 为该区间的左右端点。

N<=500000,M<=200000,0≤li≤ri≤10^9

Output

只有一行，包含一个正整数，即最小花费。

Sample Input

6 3
3 5
1 2
3 4
2 2
1 5
1 4

Sample Output

思路很神的乱搞题。

如果不管复杂度，我们可以考虑先将所有区间离散化，之后按照区间长度排序。然后从左往右扫，以每个区间为起始区间，尝试逐个加入之后的区间。怎么加入呢？用一个数组表示覆盖层数，将它左端点到右端点之间的所有点+1，表示多覆盖了一层。当有一个点被覆盖到m层时，统计一下目前的最靠右区间与起始区间的长度差更新答案。实际上，我们并不管具体选了哪些区间，只管能更新答案的最大长度的和最小长度的两个，这样只要保证选择合法即可，不用讨论具体选择。

(博主写到这里，冥思苦想40min，还是没证出来它的正确性，所以咕了)

(之后线段树优化一下区间加法就好了)

不要脸的博主又回来了。之前一直想不明白的原因在于纠结它会不会因为想找最优而漏解导致输出-1的情况出错，这实际上是不可能的。如果你从左往右扫到n都没有更新答案，就说明确实没有方案可以满足一个点被覆盖m次，因为即使是单调指针这么全扫一遍也能够考虑到所有情况。

至于线段树优化，其实就是用一个区间加法和全局最大值查询(所以没必要写区间查询的函数)。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ls(k) k<<1
#define rs(k) k<<1|1
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
const int N=1000005;
int n,m,c[N<<1],tot,top,ans=0x3f3f3f3f;
struct node
{
    int l,r,len; 
}q[N];
int cmp(node x,node y)
{
    return x.len<y.len;
}
int maxx[N<<2],lz[N<<2];
void down(int k,int l,int r)
{
    if(l==r)
    {
        lz[k]=0;
        return ;
    }
    lz[ls(k)]+=lz[k];lz[rs(k)]+=lz[k];
    maxx[ls(k)]+=lz[k];maxx[rs(k)]+=lz[k];
    lz[k]=0;
}
void add(int k,int l,int r,int L,int R,int val)
{
    if(L<=l&&R>=r)
    {
        maxx[k]+=val;
        lz[k]+=val;
        return ;
    }
    int mid=l+r>>1;
    if(lz[k])down(k,l,r);
    if(L<=mid)add(ls(k),l,mid,L,R,val);
    if(R>mid)add(rs(k),mid+1,r,L,R,val);
    maxx[k]=max(maxx[ls(k)],maxx[rs(k)]);
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
        q[i].l=read(),q[i].r=read(),q[i].len=q[i].r-q[i].l,c[++tot]=q[i].l,c[++tot]=q[i].r;
    sort(c+1,c+tot+1);
    tot=unique(c+1,c+tot+1)-c-1;
    for(int i=1;i<=n;i++)
        q[i].l=lower_bound(c+1,c+tot+1,q[i].l)-c,q[i].r=lower_bound(c+1,c+tot+1,q[i].r)-c;
    sort(q+1,q+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        while(maxx[1]<m&&top<n)
            top++,add(1,1,tot,q[top].l,q[top].r,1);
        if(maxx[1]==m)ans=min(ans,q[top].len-q[i].len);
        add(1,1,tot,q[i].l,q[i].r,-1);
    }
    if(ans==0x3f3f3f3f)puts("-1");
    else cout<<ans<<endl;
    return 0;
}