luogu_P1712 [NOI2016]区间

传送门：https://www.luogu.org/problem/P1712

学到了一种据说是普及组的思想--取尺法。（具体是啥忘了。。。。。。好像是一种很优秀的枚举方法。

这道题就是先把区间按照区间长度排个序  （好像有了单调性好多问题就很简单了

然后把区间计算到答案里 （何为计算到贡献里？ 就是这个区间里的点被覆盖次数++

当发现有一个点出现到达m次然后更新答案

再把之前加入的区间贡献减去（类似队列..........为什么能直接把贡献减去呢？因为没用了.......后面的区间长度只会更长，而它却比别人都短......所以说没用了对吧

然后这道题离散化一下，用线段树维护被覆盖次数的最大值就可以了

#include<cstdio>
#include<algorithm>
#define R register
#define ls(p) p<<1
#define rs(p) p<<1|1
using namespace std;
int n,m,lsh[1001000],mx,ans=1e9;
struct qqq{
    int l,r,len;
    inline bool operator <(const qqq i)  const{
        return len<i.len;
    }
}ln[500100];
struct ddd{
    int l,r,lazy,cnt;
}t[4001000];
inline void down(int p){
    if(t[p].lazy){
        t[ls(p)].cnt+=t[p].lazy;
        t[ls(p)].lazy+=t[p].lazy;
        t[rs(p)].cnt+=t[p].lazy;
        t[rs(p)].lazy+=t[p].lazy;
        t[p].lazy=0;
    }
}
inline void update(int p){
    t[p].cnt=max(t[ls(p)].cnt,t[rs(p)].cnt);
    return;
}
inline void build(int p,int l,int r){
    t[p].l=l;t[p].r=r;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    return;
}
inline void change(int p,int l,int r,int v){
    if(t[p].l>=l&&t[p].r<=r){
        t[p].cnt+=v;
        t[p].lazy+=v;
        return;
    }
    down(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(mid>=l) change(ls(p),l,r,v);
    if(mid< r) change(rs(p),l,r,v);
    update(p);
}
int main (){
    scanf("%d%d",&n,&m);
    for(R int i=1;i<=n;i++){
        scanf("%d%d",&ln[i].l,&ln[i].r);
        lsh[++mx]=ln[i].l;lsh[++mx]=ln[i].r;
        ln[i].len=ln[i].r-ln[i].l;
    }
    sort(lsh+1,lsh+1+mx);
    mx=unique(lsh+1,lsh+1+mx)-lsh-1;
    build(1,1,mx);
    for(R int i=1;i<=n;i++){
        ln[i].l=lower_bound(lsh+1,lsh+1+mx,ln[i].l)-lsh;
        ln[i].r=lower_bound(lsh+1,lsh+1+mx,ln[i].r)-lsh;
    }
    sort(ln+1,ln+1+n);
    int li=0;
    for(R int i=1;i<=n;i++){
        change(1,ln[i].l,ln[i].r,1);
        if(t[1].cnt==m){
            while(t[1].cnt==m){
                li++;
                change(1,ln[li].l,ln[li].r,-1);
            }
            ans=min(ans,ln[i].len-ln[li].len);    
        }
    }
    printf("%d
",ans==1e9?-1:ans);
    return 0;
}