【BZOJ4653】【NOI2016】区间

~~今年NOI也有水题好开心啊~~

离散化，按区间长度排序

枚举最长区间，用线段树维护当前所有区间覆盖的点，那么只要有至少一个点的权值大于等于\(m\)即可，也就是整个区间最值

显然枚举最长区间时最短区间是单增的。用单调队列即可。

// <4653.cpp> - Wed Aug  3 22:16:21 2016
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=500010;
const int INF=2e9;
struct num{
    int x,p;
    bool r;
    num(){}
    num(int a,int b,bool c){x=a,p=b,r=c;}
    bool operator <(const num b) const{return x<b.x;}
}a[MAXN<<1];
struct noob{
    int l,r,len;
    bool operator <(const noob b) const{return len<b.len;}
}d[MAXN];
int n,pos,val[MAXN<<3],lazy[MAXN<<3];
void add(int l,int r,int x,int p,int L=1,int R=pos){
    if(l==L&&r==R){
        val[p]+=x;
        lazy[p]+=x;
        return;
    }
    int M=L+R>>1;
    if(l<=M)add(l,min(M,r),x,p<<1,L,M);
    if(M+1<=r)add(max(l,M+1),r,x,p<<1|1,M+1,R);
    val[p]=max(val[p<<1],val[p<<1|1])+lazy[p];
}
int main(){
    n=gi();int m=gi(),tot=0;
    for(int i=1;i<=n;i++){
        a[++tot]=num(gi(),i,0);
        a[++tot]=num(gi(),i,1);
    }
    sort(a+1,a+tot+1);
    pos=0;
    for(int i=1;i<=tot;i++){
        if(i==1||a[i].x!=a[i-1].x)a[++pos]=a[i];
        if(a[i].r)d[a[i].p].r=pos;
        else d[a[i].p].l=pos;
    }
    for(int i=1;i<=n;i++)d[i].len=a[d[i].r].x-a[d[i].l].x;
    sort(d+1,d+n+1);
    int ans=INF,ps=1;
    for(int i=1;i<=n;i++){
        add(d[i].l,d[i].r,1,1);
        for(;val[1]>=m;ps++){
            ans=min(ans,d[i].len-d[ps].len);
            add(d[ps].l,d[ps].r,-1,1);
        }
    }
    printf("%d",ans==INF?-1:ans);
    return 0;
}

// <4653.cpp> - Wed Aug 3 22:16:21 2016

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=500010;

const int INF=2e9;

struct num{

int x,p;

bool r;

num(){}

num(int a,int b,bool c){x=a,p=b,r=c;}

bool operator <(const num b) const{return x<b.x;}

}a[MAXN<<1];

struct noob{

int l,r,len;

bool operator <(const noob b) const{return len<b.len;}

}d[MAXN];

int n,pos,val[MAXN<<3],lazy[MAXN<<3];

void add(int l,int r,int x,int p,int L=1,int R=pos){

if(l==L&&r==R){

val[p]+=x;

lazy[p]+=x;

return;

}

int M=L+R>>1;

if(l<=M)add(l,min(M,r),x,p<<1,L,M);

if(M+1<=r)add(max(l,M+1),r,x,p<<1|1,M+1,R);

val[p]=max(val[p<<1],val[p<<1|1])+lazy[p];

}

int main(){

n=gi();int m=gi(),tot=0;

for(int i=1;i<=n;i++){

a[++tot]=num(gi(),i,0);

a[++tot]=num(gi(),i,1);

}

sort(a+1,a+tot+1);

pos=0;

for(int i=1;i<=tot;i++){

if(i==1||a[i].x!=a[i-1].x)a[++pos]=a[i];

if(a[i].r)d[a[i].p].r=pos;

else d[a[i].p].l=pos;

}

for(int i=1;i<=n;i++)d[i].len=a[d[i].r].x-a[d[i].l].x;

sort(d+1,d+n+1);

int ans=INF,ps=1;

for(int i=1;i<=n;i++){

add(d[i].l,d[i].r,1,1);

for(;val[1]>=m;ps++){

ans=min(ans,d[i].len-d[ps].len);

add(d[ps].l,d[ps].r,-1,1);

}

printf("%d",ans==INF?-1:ans);

return 0;

}