数据结构（线段树）：NOI 2016 区间

【问题描述】

【输入格式】

【输出格式】

【样例输入】

【样例输出】

【样例说明】

【更多样例】

下载

【样例 2 输入输出】

见目录下的 interval/interval2.in 与 interval/interval2.ans。

【样例 3 输入输出】

见目录下的 interval/interval3.in 与 interval/interval3.ans。

【子任务】

【来源】

NOI2016 Day2 T1

　　这道题目，第一次做我没有做出来，当时以为好难，都对NOI都失去信心了。

　　思路是这样的，先是一定要离散化，不然就不能处理了，接着按权值排序，用一种类似尺取法的方法去O（N）扫一遍，期间用O（logN）维护被覆盖最多次的位置被覆盖的次数。

　　仔细想想还是可以感觉到这个尺取法是对的……

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 #define mid ((l+r)>>1)
 6 using namespace std;
 7 const int maxn=1000010;
 8 const int INF=1000000000;
 9 int Mx[maxn<<2],sum[maxn<<2],ans=INF,n,m,N;
10 int la[maxn],lb[maxn],b[maxn],p[maxn],kl[maxn];
11 bool cmp(int a,int b){return kl[a]<kl[b];}
12 void Modify(int x,int l,int r,int a,int b,int v){
13     if(l>=a&&r<=b){Mx[x]+=v;sum[x]+=v;return;}
14     if(mid>=a)Modify(x<<1,l,mid,a,b,v);
15     if(mid<b)Modify(x<<1|1,mid+1,r,a,b,v);
16     Mx[x]=max(Mx[x<<1],Mx[x<<1|1])+sum[x];
17 }
18 int main(){
19     freopen("interval.in","r",stdin);
20     freopen("interval.out","w",stdout);
21     scanf("%d%d",&n,&m);
22     for(int i=1;i<=n;p[i]=i,i++){
23         scanf("%d%d",&la[i],&lb[i]);
24         b[++N]=la[i];b[++N]=lb[i];
25         kl[i]=lb[i]-la[i]+1;
26     }    
27     sort(p+1,p+n+1,cmp);sort(b+1,b+N+1);
28     N=unique(b+1,b+N+1)-b-1;
29     for(int t=1;t<=n;t++){int i=p[t];
30         la[i]=lower_bound(b+1,b+N+1,la[i])-b;
31         lb[i]=lower_bound(b+1,b+N+1,lb[i])-b;
32     }
33     for(int i=1,j=0;j<n||Mx[1]==m&&j==n;){
34         while(Mx[1]<m&&j<n)++j,Modify(1,1,N,la[p[j]],lb[p[j]],1);
35         while(Mx[1]==m&&i<=n)ans=min(ans,kl[p[j]]-kl[p[i]]),Modify(1,1,N,la[p[i]],lb[p[i]],-1),i++;
36     }
37     if(ans==INF)ans=-1;
38     printf("%d
",ans);
39     return 0;
40 }