bzoj4662: Snow

#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;
}