bzoj1904: Musical Water-fence-LMLPHP

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

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

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