#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,b[1000100],tot;
struct node {
int l,r,len;
}a[500500];
bool cmp(node a,node b) {
return a.len<b.len;
}
int t[1000100<<2],tag[1000100<<2];
void push_down(int p) {
t[p<<1]+=tag[p],tag[p<<1]+=tag[p];
t[p<<1|1]+=tag[p],tag[p<<1|1]+=tag[p];
tag[p]=0;
}
void update(int p,int l,int r,int x,int y,int k) {
if(x<=l&&r<=y) {
t[p]+=k,tag[p]+=k;return ;
}
push_down(p);
int mid=l+r>>1;
if(x<=mid) update(p<<1,l,mid,x,y,k);
if(y>mid) update(p<<1|1,mid+1,r,x,y,k);
t[p]=max(t[p<<1],t[p<<1|1]);
}
signed main() {
cin>>n>>m;
for(int i=1;i<=n;i++) {
cin>>a[i].l>>a[i].r;
b[++tot]=a[i].l,b[++tot]=a[i].r;
a[i].len=a[i].r-a[i].l+1;
// cout<<a[i].len<<" ";
}
sort(b+1,b+1+tot);
int len=unique(b+1,b+1+tot)-b-1;
// cout<<len<<" ";
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++) {
a[i].l=lower_bound(b+1,b+1+len,a[i].l)-b;
a[i].r=lower_bound(b+1,b+1+len,a[i].r)-b;
// cout<<a[i].l<<" "<<a[i].r<<" "<<a[i].len<<endl;
}
int p1=1,p2=0,ans=2147483647;
while(p1<=n&&p2<=n) {
while(t[1]>=m&&p1<=p2) {
ans=min(ans,a[p2].len-a[p1].len);
update(1,1,len,a[p1++].l,a[p1].r,-1);
}
while(t[1]<m&&p2<n) update(1,1,len,a[p2].l,a[++p2].r,1);
if(t[1]<m) break;
// cout<<p1<<" "<<p2<<endl;
}
if(ans!=2147483647) cout<<ans;
else cout<<-1;
return 0;
}
上述代码中
while(t[1]<m&&p2<n) update(1,1,len,a[p2].l,a[++p2].r,1);
或
++p2,while(t[1]<m&&p2<n) update(1,1,len,a[p2].l,a[p2].r,1);
是正确的
而
while(t[1]<m&&p2<n) update(1,1,len,a[++p2].l,a[p2].r,1);
是错误的