学习离线思想 [CSP-J 2022 山东] 部署

[CSP-J 2022 山东] 部署

今天学习一下离线思想.

所谓离线, 就是等你操作完了后再问你问题, 每一次操作时间复杂度可能很大, 我们可以把操作堆起来最后一遍完成.

我们不妨记录两个内容, 一个是操作一在节点 \(u\) 要求增加的兵, 不妨将其设为 \(f(u)\); 一个是操作二在节点 \(u\) 要求增加的兵, 不妨将其设为 \(g(u)\).

我们首先记录所有操作,

for(int op,x,y;m--;){std::cin>>op>>x>>y;if(op==1)f[x]+=y;else g[x]+=y;
}

我们记录完之后, 就是要统计答案了. 我们不妨先思考操作二该怎么统计.
首先对于节点 \(u\) 而言, 其兵力增加就是 \(g(u)\), 而对于其子节点和祖先而言, 兵力都要增加 \(g(u)\).

void dfs(int u,int fa){ans[u]+=g[u];for(auto v:e[u]){ans[v]+=g[u];//祖先兵力也要增加, 故能跑的点兵力都要增加 g(u)if(v^fa)dfs(v,u);//显然深搜不能回到祖先}
}

我们再思考操作一该怎么统计.
首先对于节点 \(u\) 而言, 其增加的兵力就是 \(f(u)\). 但问题来了, 它的子树都要增加 \(f(u)\). 我们把增加的 \(f(u)\) 向下传即可.

void dfs(int u,int fa,LL down){ans[u]+=f[u]+down;for(auto v:e[u])if(v^fa)dfs(v,u,down+f[u]);
}

最后展示总代码, 当然肯定与上述有部分出入.

#include<iostream>
#include<vector>
#define P(A) A=-~A
#define NUMBER1 1000000
typedef long long LL;
typedef std::pair<int,LL> PLL;
int n;
LL ans[NUMBER1+5];
std::vector<std::vector<int>>e;
PLL c[NUMBER1+5];
void dfs(int u,int fa){ans[u]+=c[u].first+c[u].second;for(auto v:e[u]){ans[v]+=c[u].second;if(v^fa){c[v].first+=c[u].first;	dfs(v,u);}}
}
signed main(){std::cin.tie(nullptr)->std::ios::sync_with_stdio(false);std::cout.tie(nullptr);std::cin>>n;e.assign(n+1,std::vector<int>());for(int i=1;i<=n;P(i))std::cin>>ans[i];for(int i=1,u,v;i<n;P(i)){std::cin>>u>>v;e[u].push_back(v);e[v].push_back(u);}int m,q;std::cin>>m;for(int op,x,y;m--;){std::cin>>op>>x>>y;if(op==1)c[x].first+=y;else c[x].second+=y;}dfs(1,0);std::cin>>q;for(int u;q--;){std::cin>>u;std::cout<<ans[u]<<'\n';}return 0;
}