首页 > 代码库 > BZOJ4712 : 洪水
BZOJ4712 : 洪水
首先不难列出DP方程：
$dp[x]=\min(w[x],h[x])$
$h[x]=\sum dp[son]$
当$w[x]$增加时，显然$dp[x]$不会减少，那么我们求出$dp[x]$的增量$delta$，若$delta=0$那么什么都不需要做。
对于$x$来说，它的$h$值不变。
对于$x$的父亲$y$到某个祖先$z$路径上的所有点来说，它们都满足$h[i]+delta\leq w[i]$，那么这些点的$h$值都要加上$delta$。
对于$u=father[z]$来说，这个点的$h$值也要加上$delta$，但是要重新计算DP值。
这将形成一个循环的过程，不断对$h$数组进行修正即可。
为了得到$z$，需要沿着重链往上爬，对于每条重链在线段树中二分查找。
如果一个区间内$\min(w[i]-h[i])\geq delta$，那么整段区间都可行。
因此在线段树上每个点维护两个值：
$val$：$\min(w[i]-h[i])$
$tag$：区间内所有点$h$值要加上多少
对于叶子节点来说，$tag$实际上就是$h$值，因此不需要额外维护$h$值。
一个点要重新计算DP值，当且仅当它的孩子的总代价超过了自己本身的$w$，并且一旦超过，在下次修改这个点的$w$之前DP值将一直是$w$。
因此每个点一开始会贡献一个可能的重新计算次数，每次修改也会贡献一个。
而暴力修改的次数不会超过所有操作贡献的可能导致暴力的次数，所以暴力次数为$O(n+m)$。
总时间复杂度$O((n+m)\log^2n)$。
#include<cstdio>typedef long long ll;const int N=200010,M=524300;const ll inf=1LL<<60;char op;int n,m,i,x,y,g[N],v[N<<1],nxt[N<<1],ed;int f[N],size[N],son[N],top[N],loc[N],q[N],dfn;ll w[N],z,dp[N],h[N],val[M],tag[M];inline void read(int&a){char c;while(!(((c=getchar())>=‘0‘)&&(c<=‘9‘)));a=c-‘0‘;while(((c=getchar())>=‘0‘)&&(c<=‘9‘))(a*=10)+=c-‘0‘;}inline void read(ll&a){char c;while(!(((c=getchar())>=‘0‘)&&(c<=‘9‘)));a=c-‘0‘;while(((c=getchar())>=‘0‘)&&(c<=‘9‘))(a*=10)+=c-‘0‘;}inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}inline ll min(ll a,ll b){return a<b?a:b;}void dfs(int x){ size[x]=1; for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]){ f[v[i]]=x; dfs(v[i]); size[x]+=size[v[i]]; h[x]+=dp[v[i]]; if(size[v[i]]>size[son[x]])son[x]=v[i]; } if(size[x]==1)h[x]=inf; dp[x]=min(w[x],h[x]);}void dfs2(int x,int y){ q[loc[x]=++dfn]=x;top[x]=y; if(son[x])dfs2(son[x],y); for(int i=g[x];i;i=nxt[i])if(v[i]!=son[x]&&v[i]!=f[x])dfs2(v[i],v[i]);}inline void tag1(int x,ll p){val[x]-=p;tag[x]+=p;}inline void pb(int x){if(tag[x])tag1(x<<1,tag[x]),tag1(x<<1|1,tag[x]),tag[x]=0;}inline void up(int x){val[x]=min(val[x<<1],val[x<<1|1]);}void build(int x,int a,int b){ if(a==b){ int y=q[a]; val[x]=w[y]-h[y]; tag[x]=h[y]; return; } int mid=(a+b)>>1; build(x<<1,a,mid),build(x<<1|1,mid+1,b); up(x);}ll ask(int x,int a,int b,int c){ if(a==b)return tag[x]; pb(x); int mid=(a+b)>>1; return c<=mid?ask(x<<1,a,mid,c):ask(x<<1|1,mid+1,b,c);}void changew(int x,int a,int b,int c){ if(a==b){val[x]=w[q[a]]-tag[x];return;} pb(x); int mid=(a+b)>>1; if(c<=mid)changew(x<<1,a,mid,c);else changew(x<<1|1,mid+1,b,c); up(x);}void changeh(int x,int a,int b,int c,int d,ll p){ if(c<=a&&b<=d){tag1(x,p);return;} pb(x); int mid=(a+b)>>1; if(c<=mid)changeh(x<<1,a,mid,c,d,p); if(d>mid)changeh(x<<1|1,mid+1,b,c,d,p); up(x);}int get(int x,int a,int b,int c,int d,ll p){ if(c<=a&&b<=d){ if(val[x]>=p)return a; if(a==b)return 0; } pb(x); int mid=(a+b)>>1,t; if(d<=mid)return get(x<<1,a,mid,c,d,p); if(c>mid)return get(x<<1|1,mid+1,b,c,d,p); t=get(x<<1|1,mid+1,b,c,d,p); if(!t||t>mid+1)return t; t=get(x<<1,a,mid,c,d,p); return t?t:mid+1;}inline ll DP(int x){return min(w[x],ask(1,1,n,loc[x]));}inline int gety(int x,ll p){ int t=x;x=f[x]; while(x){ int o=get(1,1,n,loc[top[x]],loc[x],p); if(!o)break; if(o>loc[top[x]])return q[o]; t=top[x]; x=f[t]; } return t;}inline void chain(int x,int y,ll p){ while(top[x]!=top[y])changeh(1,1,n,loc[top[x]],loc[x],p),x=f[top[x]]; changeh(1,1,n,loc[y],loc[x],p);}inline void modify(int x,ll y){ ll t=DP(x); w[x]+=y; changew(1,1,n,loc[x]); ll d=DP(x)-t; if(!d)return; while(f[x]){ int y=gety(x,d); if(x!=y)chain(f[x],y,d); x=f[y]; if(!x)return; t=DP(x); chain(x,x,d); d=DP(x)-t; if(!d)return; }}int main(){ read(n); for(i=1;i<=n;i++)read(w[i]); for(i=1;i<n;i++)read(x),read(y),add(x,y),add(y,x); dfs(1);dfs2(1,1); build(1,1,n); read(m); while(m--){ while((op=getchar())!=‘Q‘&&op!=‘C‘);read(x); if(op==‘Q‘)printf("%lld\n",DP(x));else read(z),modify(x,z); } return 0;}
BZOJ4712 : 洪水
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。