https://www.lydsy.com/JudgeOnline/problem.php?id=4653
https://www.luogu.org/problemnew/show/P1712
在数轴上有 n个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间，使得这 m个区间共同包含至少一个位置。换句话说，就是使得存在一个 x，使得对于每一个被选中的区间 [li,ri]，都有 li≤x≤ri。
对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li，即等于它的右端点的值减去左端点的值。求所有合法方案中最小的花费。如果不存在合法的方案，输出 −1。
（天哪我终于会做套路题了……虽然对于判断是否合法的时候没想到线段树……）
看复杂度是O(nlogn)猜想可能又是枚举左端点找右端点的套路。
然而相比于一个点被覆盖m次，更难处理的是这个答案的运算。
于是我们将区间按照权值排序，接着就是两个指针不断扩大，当合法的时候更新一下答案就行了。
那么如何维护一个点被最多被覆盖了多少次呢？线段树呗。
注意空间不要开小了-=-
#include<cmath> #include<stack> #include<queue> #include<cstdio> #include<cctype> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int INF=2e9; const int N=5e5+5; inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } struct range{ int l,r,w; }g[N]; int n,m,lim,b[2*N],tr[8*N],lz[8*N]; inline bool cmp(range a,range b){ return a.w<b.w; } inline void LSH(){ sort(b+1,b+lim+1); lim=unique(b+1,b+lim+1)-b-1; for(int i=1;i<=n;i++){ g[i].l=lower_bound(b+1,b+lim+1,g[i].l)-b; g[i].r=lower_bound(b+1,b+lim+1,g[i].r)-b; } } inline void push(int a){ if(!lz[a])return; lz[a<<1]+=lz[a];lz[a<<1|1]+=lz[a]; tr[a<<1]+=lz[a];tr[a<<1|1]+=lz[a]; lz[a]=0; } void insert(int a,int l,int r,int l1,int r1,int w){ if(r<l1||r1<l)return; if(l1<=l&&r<=r1){ tr[a]+=w;lz[a]+=w; return; } push(a); int mid=(l+r)>>1; insert(a<<1,l,mid,l1,r1,w); insert(a<<1|1,mid+1,r,l1,r1,w); tr[a]=max(tr[a<<1],tr[a<<1|1]); } int main(){ n=read(),m=read(); for(int i=1;i<=n;i++){ g[i].l=b[++lim]=read(); g[i].r=b[++lim]=read(); g[i].w=g[i].r-g[i].l; } LSH(); sort(g+1,g+n+1,cmp); int l=1,ans=INF; for(int l=1,r=0;l<=n;l++){ while(r<n&&tr[1]<m){ r++; insert(1,1,lim,g[r].l,g[r].r,1); } if(tr[1]>=m)ans=min(ans,g[r].w-g[l].w); insert(1,1,lim,g[l].l,g[l].r,-1); } printf("%d\n",ans==INF?-1:ans); return 0; }
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++