传送门:https://www.luogu.org/problem/P1712
学到了一种据说是普及组的思想--取尺法。(具体是啥忘了。。。。。。好像是一种很优秀的枚举方法。
这道题就是先把区间按照区间长度排个序 (好像有了单调性好多问题就很简单了
然后把区间计算到答案里 (何为计算到贡献里? 就是这个区间里的点被覆盖次数++
当发现有一个点出现到达m次然后更新答案
再把之前加入的区间贡献减去(类似队列..........为什么能直接把贡献减去呢?因为没用了.......后面的区间长度只会更长,而它却比别人都短......所以说没用了对吧
然后这道题离散化一下,用线段树维护被覆盖次数的最大值就可以了
#include<cstdio> #include<algorithm> #define R register #define ls(p) p<<1 #define rs(p) p<<1|1 using namespace std; int n,m,lsh[1001000],mx,ans=1e9; struct qqq{ int l,r,len; inline bool operator <(const qqq i) const{ return len<i.len; } }ln[500100]; struct ddd{ int l,r,lazy,cnt; }t[4001000]; inline void down(int p){ if(t[p].lazy){ t[ls(p)].cnt+=t[p].lazy; t[ls(p)].lazy+=t[p].lazy; t[rs(p)].cnt+=t[p].lazy; t[rs(p)].lazy+=t[p].lazy; t[p].lazy=0; } } inline void update(int p){ t[p].cnt=max(t[ls(p)].cnt,t[rs(p)].cnt); return; } inline void build(int p,int l,int r){ t[p].l=l;t[p].r=r; if(l==r) return; int mid=(l+r)>>1; build(ls(p),l,mid); build(rs(p),mid+1,r); return; } inline void change(int p,int l,int r,int v){ if(t[p].l>=l&&t[p].r<=r){ t[p].cnt+=v; t[p].lazy+=v; return; } down(p); int mid=(t[p].l+t[p].r)>>1; if(mid>=l) change(ls(p),l,r,v); if(mid< r) change(rs(p),l,r,v); update(p); } int main (){ scanf("%d%d",&n,&m); for(R int i=1;i<=n;i++){ scanf("%d%d",&ln[i].l,&ln[i].r); lsh[++mx]=ln[i].l;lsh[++mx]=ln[i].r; ln[i].len=ln[i].r-ln[i].l; } sort(lsh+1,lsh+1+mx); mx=unique(lsh+1,lsh+1+mx)-lsh-1; build(1,1,mx); for(R int i=1;i<=n;i++){ ln[i].l=lower_bound(lsh+1,lsh+1+mx,ln[i].l)-lsh; ln[i].r=lower_bound(lsh+1,lsh+1+mx,ln[i].r)-lsh; } sort(ln+1,ln+1+n); int li=0; for(R int i=1;i<=n;i++){ change(1,ln[i].l,ln[i].r,1); if(t[1].cnt==m){ while(t[1].cnt==m){ li++; change(1,ln[li].l,ln[li].r,-1); } ans=min(ans,ln[i].len-ln[li].len); } } printf("%d\n",ans==1e9?-1:ans); return 0; }View Code