首页 > 代码库 > bzoj4662: Snow

bzoj4662: Snow

2024-09-01 08:36:03   218人阅读

Description

2333年的某一天，临冬突降大雪，主干道已经被雪覆盖不能使用。城
主 囧·雪 决定要对主干道进行一次清扫。
临冬城的主干道可以看为一条数轴。囧·雪 一共找来了n个清理工，第
i个清理工的工作范围为[li,ri]，也就是说这个清理工会把[li,ri]这一
段主干道清理干净(当然已经被清理过的部分就被忽略了)。当然有可能主
干道不能全部被清理干净，不过这也没啥关系。
虽然 囧·雪 啥都不知道，但是他还是保证了不会出现某一个清理工的
工作范围被另一个清理工完全包含的情况(不然就太蠢了)。
作为临冬城主，囧·雪 给出了如下的清扫方案：
在每一天开始的时候，每一个还没有工作过的清理工会观察自己工作
范围内的道路，并且记下工作范围内此时还没有被清理的道路的长度(称
为这个清理工的工作长度)。然后 囧·雪 会从中选择一个工作长度最小的
清理工(如果两个清理工工作长度相同，那么就选择编号小的清理工)。然
后被选择的这个清理工会清理自己的工作范围内的道路。为了方便检查工
作质量，囧·雪 希望每一天只有一个清理工在工作。
你要注意，清理工的工作长度是可能改变的，甚至有可能变成0。尽管
如此，这个清理工也还是会在某一天工作。
现在，囧·雪 想要知道每一天都是哪个清理工在工作？

Input

第一行两个整数t,n。分别表示主干道的长度(也就是说，主干道是数
轴上[1,t]的这一段)以及清理工的人数。
接下来n行，每行两个整数li,ri。意义如题。
n<=3*10^5, 1<=li<ri<=t<=10^9，保证输入的li严格递增

Output

输出n行，第i行表示第i天工作的清理工的编号。
区间互不包含说明左端点升序时右端点严格单调，区间端点离散化，用线段树维护按左端点排序后工作长度的最小值，每次查出最小值后将其删去并枚举这次清扫的区间，对应在线段树中是连续的一段，可以标记实现区间减。
 
#include<cstdio>#include<algorithm>const int N=300077;char buf[10000007],*ptr=buf-1;int _(){    int x=0,c=*++ptr;    while(c<48)c=*++ptr;    while(c>47)x=x*10+c-48,c=*++ptr;    return x;}int min(int a,int b){return a<b?a:b;}int mx,n,ls[N],rs[N],xs[N*2],xp=0,ans,f[N*2],_l,_r,_a;struct node{    node*lc,*rc;    int L,R,mn,a;    void up(){mn=min(lc->mn,rc->mn);}    void dn(){        if(a){            lc->mn+=a;            lc->a+=a;            rc->mn+=a;            rc->a+=a;            a=0;        }    }    void dec(){        if(_l<=L&&R<=_r){            mn+=_a;            a+=_a;            return;        }        int M=L+R>>1;        dn();        if(_l<=M)lc->dec();        if(_r>M)rc->dec();        up();    }    void cal(){        if(L==R){            ans=L;            mn=0x7fffffff;            return;        }        dn();        (lc->mn<=rc->mn?lc:rc)->cal();        up();    }}ns[N*2],*np=ns,*rt;node*build(int L,int R){    node*w=np++;    w->L=L;w->R=R;    if(L==R){        w->mn=rs[L]-ls[L];    }else{        int M=L+R>>1;        w->lc=build(L,M);        w->rc=build(M+1,R);        w->up();    }    return w;}int get(int x){    int a=x,c;    while(x!=f[x])x=f[x];    while(x!=f[a])c=f[a],f[a]=x,a=c;    return x;}int main(){    fread(buf,1,sizeof(buf),stdin);    mx=_();n=_();    for(int i=1;i<=n;++i){        ls[i]=_();        rs[i]=_();    }    rt=build(1,n);    int p1=1,p2=1;    while(p1<=n&&p2<=n){        if(ls[p1]<rs[p2])xs[++xp]=ls[p1],ls[p1++]=xp;        else if(ls[p1]>rs[p2])xs[++xp]=rs[p2],rs[p2++]=xp;        else xs[++xp]=ls[p1],ls[p1++]=rs[p2++]=xp;    }    while(p1<=n)xs[++xp]=ls[p1],ls[p1++]=xp;    while(p2<=n)xs[++xp]=rs[p2],rs[p2++]=xp;    for(int i=1;i<=xp;++i)f[i]=i;    for(int i=1;i<=n;++i){        rt->cal();        printf("%d\n",ans);        for(int p=get(ls[ans]);p<rs[ans];p=f[p]=get(p+1)){            _l=std::upper_bound(rs+1,rs+n+1,p)-rs;            _r=std::upper_bound(ls+1,ls+n+1,p)-ls-1;            _a=xs[p]-xs[p+1];            rt->dec();        }    }    return 0;}

 

bzoj4662: Snow


联系
我们