额...
首先,看到这道题,第一想法就是二分答案+线段树...
兴高采烈的认为我一定能AC,之后发现n是500000...
nlog^2=80%,亲测可过...
由于答案是求满足题意的最大长度-最小长度最小,那么我们可以考虑将区间按长度排序
之后,因为我们是需要最大最小,所以,我们必定选择在排完序的区间上取连续的一段是最优情况(起码不会比别的差)
因此,考虑双指针扫一下就可以了...
是不是很水?
由于懒得写离散化,一开始写的动态开点线段树,我*****什么鬼?mle?!256mb开不下!
loj+洛谷上95%,附上代码...
#include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <cstdlib> #include <iostream> #include <queue> using namespace std; #define N 500005 #define lson l,m,tr[rt].ls #define rson m+1,r,tr[rt].rs #define PushUp(rt) tr[rt].maxx=max(tr[tr[rt].ls].maxx,tr[tr[rt].rs].maxx) struct no { int ls,rs,maxx,add; }tr[N*40]; int n,m,ans,cnt; struct node { int l,r,len; }a[N]; bool cmp(const node &a,const node &b) { return a.len<b.len; } void PushDown(int rt) { if(tr[rt].add) { if(!tr[rt].ls)tr[rt].ls=++cnt; if(!tr[rt].rs)tr[rt].rs=++cnt; tr[tr[rt].ls].maxx+=tr[rt].add; tr[tr[rt].rs].maxx+=tr[rt].add; tr[tr[rt].ls].add+=tr[rt].add; tr[tr[rt].rs].add+=tr[rt].add; tr[rt].add=0; } } void Update(int L,int R,bool c,int l,int r,int &rt) { if(!rt)rt=++cnt; if(L<=l&&r<=R) { tr[rt].maxx+=c?1:-1; tr[rt].add+=c?1:-1; return ; } PushDown(rt); int m=(l+r)>>1; if(m>=L)Update(L,R,c,lson); if(m<R)Update(L,R,c,rson); PushUp(rt); } int main() { ans=1<<30; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].l,&a[i].r); a[i].len=a[i].r-a[i].l; } sort(a+1,a+n+1,cmp); int l=1,r=0,rot=0; while(r<n) { while(tr[rot].maxx<m&&r<n){r++;Update(a[r].l,a[r].r,1,0,1<<30,rot);} if(tr[rot].maxx<m)break; while(tr[rot].maxx>=m&&l<n){Update(a[l].l,a[l].r,0,0,1<<30,rot);l++;} ans=min(a[r].len-a[l-1].len,ans); } printf("%d\n",ans==1<<30?-1:ans); return 0; }
这显然就不能AC,那么我们可以考虑用一下离散化...
离散化后,线段树的空间复杂度从(nlog(1<<30))变成(nlog(n*2))之后,空间就降下来了...
附上AC代码...
#include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <cstdlib> #include <iostream> #include <queue> using namespace std; #define N 500005 #define lson l,m,tr[rt].ls #define rson m+1,r,tr[rt].rs #define PushUp(rt) tr[rt].maxx=max(tr[tr[rt].ls].maxx,tr[tr[rt].rs].maxx) struct no { int ls,rs,maxx,add; }tr[N*10]; int p[N<<1]; int n,m,ans,cnt; struct node { int l,r,len; }a[N]; bool cmp(const node &a,const node &b) { return a.len<b.len; } void PushDown(int rt) { if(tr[rt].add) { if(!tr[rt].ls)tr[rt].ls=++cnt; if(!tr[rt].rs)tr[rt].rs=++cnt; tr[tr[rt].ls].maxx+=tr[rt].add; tr[tr[rt].rs].maxx+=tr[rt].add; tr[tr[rt].ls].add+=tr[rt].add; tr[tr[rt].rs].add+=tr[rt].add; tr[rt].add=0; } } void Update(int L,int R,bool c,int l,int r,int &rt) { if(!rt)rt=++cnt; if(L<=l&&r<=R) { tr[rt].maxx+=c?1:-1; tr[rt].add+=c?1:-1; return ; } PushDown(rt); int m=(l+r)>>1; if(m>=L)Update(L,R,c,lson); if(m<R)Update(L,R,c,rson); PushUp(rt); } int main() { ans=1<<30; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].l,&a[i].r); a[i].len=a[i].r-a[i].l; p[(i<<1)-1]=a[i].l; p[i<<1]=a[i].r; } sort(p+1,p+n*2+1); for(int i=1;i<=n;i++) { int x=lower_bound(p+1,p+n*2+1,a[i].l)-p; a[i].l=x; x=lower_bound(p+1,p+n*2+1,a[i].r)-p; a[i].r=x; } sort(a+1,a+n+1,cmp); int l=1,r=0,rot=0; while(r<n) { while(tr[rot].maxx<m&&r<n){r++;Update(a[r].l,a[r].r,1,1,n*2,rot);} if(tr[rot].maxx<m)break; while(tr[rot].maxx>=m&&l<n){Update(a[l].l,a[l].r,0,1,n*2,rot);l++;} ans=min(a[r].len-a[l-1].len,ans); } printf("%d\n",ans==1<<30?-1:ans); return 0; }
离散化什么的,用lower_bound就好了,懒得写二分查找了...反正不会tle...