【问题描述】
【输入格式】
【输出格式】
【样例输入】
6 3
3 5
1 2
3 4
2 2
1 5
1 4
【样例输出】
2
【样例说明】
【更多样例】
【样例 2 输入输出】
见目录下的 interval/interval2.in 与 interval/interval2.ans。
【样例 3 输入输出】
见目录下的 interval/interval3.in 与 interval/interval3.ans。
【子任务】
【来源】
NOI2016 Day2 T1
这道题目，第一次做我没有做出来，当时以为好难，都对NOI都失去信心了。
思路是这样的，先是一定要离散化，不然就不能处理了，接着按权值排序，用一种类似尺取法的方法去O（N）扫一遍，期间用O（logN）维护被覆盖最多次的位置被覆盖的次数。
仔细想想还是可以感觉到这个尺取法是对的……
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define mid ((l+r)>>1)
using namespace std;
const int maxn=;
const int INF=;
int Mx[maxn<<],sum[maxn<<],ans=INF,n,m,N;
int la[maxn],lb[maxn],b[maxn],p[maxn],kl[maxn];
bool cmp(int a,int b){return kl[a]<kl[b];}
void Modify(int x,int l,int r,int a,int b,int v){
if(l>=a&&r<=b){Mx[x]+=v;sum[x]+=v;return;}
if(mid>=a)Modify(x<<,l,mid,a,b,v);
if(mid<b)Modify(x<<|,mid+,r,a,b,v);
Mx[x]=max(Mx[x<<],Mx[x<<|])+sum[x];
}
int main(){
freopen("interval.in","r",stdin);
freopen("interval.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=;i<=n;p[i]=i,i++){
scanf("%d%d",&la[i],&lb[i]);
b[++N]=la[i];b[++N]=lb[i];
kl[i]=lb[i]-la[i]+;
}
sort(p+,p+n+,cmp);sort(b+,b+N+);
N=unique(b+,b+N+)-b-;
for(int t=;t<=n;t++){int i=p[t];
la[i]=lower_bound(b+,b+N+,la[i])-b;
lb[i]=lower_bound(b+,b+N+,lb[i])-b;
}
for(int i=,j=;j<n||Mx[]==m&&j==n;){
while(Mx[]<m&&j<n)++j,Modify(,,N,la[p[j]],lb[p[j]],);
while(Mx[]==m&&i<=n)ans=min(ans,kl[p[j]]-kl[p[i]]),Modify(,,N,la[p[i]],lb[p[i]],-),i++;
}
if(ans==INF)ans=-;
printf("%d\n",ans);
return ;
}