首页 > 代码库 > bzoj1904: Musical Water-fence

bzoj1904: Musical Water-fence

技术分享

找出最高的木块,假设在这块木块上无限加水,就会形成一些水池,然后才向两侧溢出

用并查集维护当前在某个位置使水向左/右流动,水会流向哪个水池或从某一侧溢出浪费,当某个水池满时更新并查集

#include<cstdio>int n,m,mx=1,n2;double ws[1000007],hs[1000007],sum[1000007],al=0,ar=0;int f[2000007],ss[1000007],sp=0;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;}void cal(int w){    if(w<n2)f[w]=w+n2;    else f[w]=w-n2;}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;++i){        scanf("%lf%lf",ws+i,hs+i);        if(hs[i]>hs[mx])mx=i;    }    ss[sp=0]=mx;    for(int i=mx-1;i;--i){        while(hs[ss[sp]]<hs[i])--sp;        ss[++sp]=i;    }    ss[++sp]=0;    n2=n+2;    for(int i=sp;i;--i){        for(int j=ss[i];j<ss[i-1];++j)f[j+1]=f[j+n2]=ss[i]+n2,sum[ss[i]]+=ws[j]*(hs[ss[i]]-hs[j]);    }    ss[sp=0]=mx;    for(int i=mx+1;i<=n;++i){        while(hs[ss[sp]]<hs[i])--sp;        ss[++sp]=i;    }    ss[++sp]=n+1;    for(int i=sp;i;--i){        for(int j=ss[i];j>ss[i-1];--j)f[j-1+n2]=f[j]=ss[i],sum[ss[i]]+=ws[j]*(hs[ss[i]]-hs[j]);    }    for(int i=1;i<=m;++i){        int x;double s,sl,sr;        scanf("%d%lf",&x,&s);        sl=sr=s/2;        while(sl){            int w=get(x);            if(w%n2==0){                al+=sl;                sl=0;            }else if(w%n2==n+1){                ar+=sl;                sl=0;            }else if(sum[w%n2]>sl){                sum[w%n2]-=sl;                sl=0;            }else{                sl-=sum[w%n2];                sum[w%n2]=0;                cal(w);            }        }        while(sr){            int w=get(x+n2);            if(w%n2==0){                al+=sr;                sr=0;            }else if(w%n2==n+1){                ar+=sr;                sr=0;            }else if(sum[w%n2]>sr){                sum[w%n2]-=sr;                sr=0;            }else{                sr-=sum[w%n2];                sum[w%n2]=0;                cal(w);            }        }    }    printf("%.3f\n%.3f",al,ar);    return 0;}

 

bzoj1904: Musical Water-fence