首页 > 代码库 > 【bzoj4765】 普通计算姬
【bzoj4765】 普通计算姬
题意
给出一棵有根树，$n$个点每个都有一个点权。$m$组操作每次可以修改一个点权或者询问编号在区间$[l,r]$的点的子树权值和的和。
Solution
我们对节点编号分块，每一块统计该块中的节点的子树权值和的和。dfs处理出修改一个节点，需要对应修改它的祖先和它的所在的哪些块。另外再开一个树状数组，树状数组中每一个元素是对应dfs的点的权值，这样我们可以求出任意子树的权值和。
对于询问，在中间的块直接统计。两侧零散的块在树状数组上暴力查询子树权值和。所以令块的大小$S=\sqrt{n/\log{n}}$，复杂度$O(n\sqrt{n\log{n}})$
细节
会爆long long
代码
// bzoj4765#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define ULL unsigned long long#define inf (1ll<<30)#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)using namespace std;const int maxn=100010;int head[maxn],L[maxn],R[maxn],t[maxn][350],pos[maxn],n,m,S,bn,cnt,dfn,Dargen;LL c[maxn],d[maxn],a[maxn];ULL s[maxn];struct edge {int to,next;}e[maxn<<1];int lowbit(int x) { return x&-x;}void add(int x,LL val) { for (int i=x;i<=n;i+=lowbit(i)) c[i]+=val;}LL query(int x) { LL res=0; for (int i=x;i;i-=lowbit(i)) res+=c[i]; return res;}void link(int u,int v) { e[++cnt]=(edge){v,head[u]};head[u]=cnt; e[++cnt]=(edge){u,head[v]};head[v]=cnt;}LL dfs(int x,int fa) { L[x]=++dfn;d[pos[x]]++; LL sum=a[x];add(L[x],a[x]); for (int i=1;i<=bn;i++) t[x][i]=d[i]; for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa) sum+=dfs(e[i].to,x); R[x]=dfn;d[pos[x]]--;s[pos[x]]+=sum; return sum;}int main() { scanf("%d%d",&n,&m); S=300;bn=n/S+(n%S!=0); for (int i=1;i<=n;i++) pos[i]=(i-1)/S+1; for (int i=1;i<=n;i++) scanf("%lld",&a[i]); for (int u,v,i=1;i<=n;i++) { scanf("%d%d",&u,&v); if ((LL)u*v==0) Dargen=u+v; else link(u,v); } dfs(Dargen,0); for (int op,x,y,i=1;i<=m;i++) { scanf("%d%d%d",&op,&x,&y); if (op==1) { LL d=y-a[x];a[x]=y; for (int j=1;j<=bn;j++) s[j]+=d*t[x][j]; add(L[x],d); } if (op==2) { ULL ans=0; if (pos[x]==pos[y]) for (int j=x;j<=y;j++) ans+=query(R[j])-query(L[j]-1); else { for (int j=pos[x]+1;j<pos[y];j++) ans+=s[j]; for (int j=x;j<=S*pos[x];j++) ans+=query(R[j])-query(L[j]-1); for (int j=(pos[y]-1)*S+1;j<=y;j++) ans+=query(R[j])-query(L[j]-1); } printf("%llu\n",ans); } } return 0;}
【bzoj4765】 普通计算姬
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。