洛谷 P1712 [NOI2016]区间（线段树）
考虑将所有的区间按长度排序
考虑怎么判断点被多少区间覆盖，这个可以离散化之后用一棵权值线段树来搞
然后维护两个指针$l,r$，当被覆盖次数最多的点的覆盖次数小于$m$时不断右移$r$，在覆盖次数大于等于$m$时不断右移$l$，然后每一次用$len[r]-len[l]$更新答案，其中$len$表示该区间的长度
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<algorithm> 5 #define inf 0x3f3f3f3f 6 using namespace std; 7 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 8 char buf[1<<21],*p1=buf,*p2=buf; 9 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} 10 template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} 11 inline int read(){ 12 #define num ch-'0' 13 char ch;bool flag=0;int res; 14 while(!isdigit(ch=getc())) 15 (ch=='-')&&(flag=true); 16 for(res=num;isdigit(ch=getc());res=res*10+num); 17 (flag)&&(res=-res); 18 #undef num 19 return res; 20 } 21 const int N=5e5+5; 22 int sum[N<<3],add[N<<3],L[N],R[N],val[N<<1],n,m,lim,cnt,ans=inf; 23 struct node{ 24 int len,id; 25 node(){} 26 node(int len,int id):len(len),id(id){} 27 inline bool operator <(const node &b)const 28 {return len<b.len;} 29 }a[N]; 30 inline void upd(int p){ 31 if(add[p]){ 32 add[p<<1]+=add[p],add[p<<1|1]+=add[p]; 33 sum[p<<1]+=add[p],sum[p<<1|1]+=add[p]; 34 add[p]=0; 35 } 36 } 37 void update(int p,int l,int r,int ql,int qr,int val){ 38 if(ql>r||qr<l) return; 39 if(ql<=l&&qr>=r) return (void)(add[p]+=val,sum[p]+=val); 40 int mid=(l+r)>>1;upd(p); 41 update(p<<1,l,mid,ql,qr,val); 42 update(p<<1|1,mid+1,r,ql,qr,val); 43 sum[p]=max(sum[p<<1],sum[p<<1|1]); 44 } 45 int main(){ 46 // freopen("testdata.in","r",stdin); 47 n=read(),m=read(); 48 for(int i=1;i<=n;++i) 49 L[i]=val[++cnt]=read(),R[i]=val[++cnt]=read(),a[i]=node(R[i]-L[i],i); 50 sort(a+1,a+1+n); 51 sort(val+1,val+1+cnt),lim=unique(val+1,val+1+cnt)-val-1; 52 for(int i=1;i<=n;++i) 53 L[i]=lower_bound(val+1,val+1+lim,L[i])-val,R[i]=lower_bound(val+1,val+1+lim,R[i])-val; 54 int l=0,r=0; 55 while(true){ 56 while(sum[1]<m&&r<n){ 57 int i=a[++r].id,u=L[i],v=R[i]; 58 update(1,1,lim,u,v,1); 59 } 60 if(sum[1]<m) break; 61 while(sum[1]>=m&&l<n){ 62 int i=a[++l].id,u=L[i],v=R[i]; 63 update(1,1,lim,u,v,-1); 64 } 65 cmin(ans,a[r].len-a[l].len); 66 } 67 printf("%d ",ans==inf?-1:ans); 68 return 0; 69 }