本文主要是介绍P1712 [NOI2016] 区间 线段树+双指针，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
// Problem:
// P1712 [NOI2016] 区间
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1712
// Memory Limit: 250 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<algorithm>
using namespace std;
const int N=5e5+10;
#define int long long
#define lc u<<1
#define rc u<<1|1
int n,m;
struct line{int l,r,len;bool operator<(const line&t){return len<t.len;};
}L[N];
struct Tree{int l,r;int cnt,add;
}tr[N*4*2];
int a[N*2];//离散化专用数组
void pushup(int u){tr[u].cnt=max(tr[lc].cnt,tr[rc].cnt);//这里比较重要
}
void pushdown(int u){if(tr[u].add){tr[lc].add+=tr[u].add;tr[rc].add+=tr[u].add;tr[lc].cnt+=tr[u].add;tr[rc].cnt+=tr[u].add;tr[u].add=0;}
}
void build(int u,int l,int r){tr[u]={l,r};if(l==r) return;int m=(l+r)>>1;build(lc,l,m);build(rc,m+1,r);//pushup(u);
}void update(int u,int l,int r,int k){if(l<=tr[u].l&&tr[u].r<=r){tr[u].add+=k;tr[u].cnt+=k;return;}pushdown(u);int m=(tr[u].l+tr[u].r)>>1;if(l<=m) update(lc,l,r,k);if(r>m) update(rc,l,r,k);pushup(u);
}signed main(){cin>>n>>m;for(int i=1;i<=n;++i){cin>>L[i].l>>L[i].r,L[i].len=L[i].r-L[i].l;a[i]=L[i].l;a[i+n]=L[i].r;}sort(a+1,a+1+2*n);//1 / 2 ???sort(L+1,L+1+n);int t=unique(a+1,a+1+2*n)-(a+1);//这个要+1，因为返回的是下一个位置for(int i=1;i<=n;++i){L[i].l=lower_bound(a+1,a+1+t,L[i].l)-a;L[i].r=lower_bound(a+1,a+1+t,L[i].r)-a;//要注意一个事减a 返回下标}build(1,1,t);int ans=1e9;for(int i=0,j=0;j<=n;){while(tr[1].cnt<m&&j<n) ++j,update(1,L[j].l,L[j].r,1);if(tr[1].cnt<m) break;while(tr[1].cnt==m&&i<j) ++i,update(1,L[i].l,L[i].r,-1);ans=min(ans,L[j].len-L[i].len);}if(ans==1e9) cout<<-1<<endl;else cout<<ans<<endl;return 0;
}一道非常规的线段树，重在思想。
为什么要用离散化？因为数据范围过大，但是数据量小
为什么要先排序？因为排序完后用双指针（尺取法）操作，距离近的已经是答案，排序顺序对答案没有影响（最小区间长度差）
为什么最后直接返回tr[1].cnt？ 因为是最大重合数，如果多次重叠，相当于+1，不同区间pushup得到最大的重叠数，用懒标记（区间重叠数的统计）
为什么双指针中右边的减左边的一定是同种？因为一直维护的大小是3，变动了就一定是最左和最优的原因
这篇关于P1712 [NOI2016] 区间 线段树+双指针的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
