首页 > 代码库 > HDU 3966（树链剖分+点修改+点查询）
HDU 3966（树链剖分+点修改+点查询）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3966
题目大意：营地的分布成树型。每个营地都有一些人，每次修改修改一条链上的所有营地的人数，每次查询单个点。
解题思路：
树链剖分基础题。
维护一个sum。
注意轻链修改时，点修改和边修改的不同。
由于树的结构与线段树点的顺序不太相同，因此需要做一个映射数组rank。故在线段树Build的时候，权值是camp[rank[l]]，rank这步的映射在dfs2的时候完成，rank[w[u]]=u;
Query单点u的时候, w[u]是其在线段树中的位置。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include "cstdio"#include "vector"#include "cstring"using namespace std;#define maxn 50005int camp[maxn],s[maxn],dep[maxn],pos[maxn],son[maxn],top[maxn],fa[maxn],w[maxn],rank[maxn],cnt,n;vector<int> G[maxn];void dfs1(int u,int pre,int d){ s[u]=1;fa[u]=pre;dep[u]=d; for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(v==pre) continue; dfs1(v,u,d+1); s[u]+=s[v]; if(son[u]!=-1||s[v]>s[son[u]]) son[u]=v; }}void dfs2(int u,int tp){ w[u]=++cnt;top[u]=tp;rank[w[u]]=u; if(son[u]==-1) return; dfs2(son[u],tp); for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(v!=son[u]&&v!=fa[u]) dfs2(v,v); }}//Segment-Tree#define lson l,mid,root<<1#define rson mid+1,r,root<<1|1int col[maxn<<2],sum[maxn<<2];void PushUp(int root){ sum[root]=sum[root<<1]+sum[root<<1|1];}void Build(int l,int r,int root){ col[root]=0; if(l==r) { sum[root]=camp[rank[l]]; return; } int mid=(l+r)>>1; Build(lson); Build(rson); PushUp(root);}void PushDown(int root,int m){ if(col[root]) { col[root<<1]+=col[root]; col[root<<1|1]+=col[root]; sum[root<<1]+=(m-(m>>1))*col[root]; sum[root<<1|1]+=(m>>1)*col[root]; col[root]=0; }}void Update(int L,int R,int v,int l,int r,int root){ if(L<=l&&r<=R) { col[root]+=v; sum[root]+=(r-l+1)*v; return; } PushDown(root,r-l+1); int mid=(l+r)>>1; if(L<=mid) Update(L,R,v,lson); if(R>mid) Update(L,R,v,rson); PushUp(root);}int Query(int p,int l,int r,int root){ if(l==r) return sum[root]; PushDown(root,r-l+1); int mid=(l+r)>>1,ret=0; if(p<=mid) ret=Query(p,lson); else ret=Query(p,rson); return ret;}void Change(int x,int y,int v){ while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); Update(w[top[x]],w[x],v,1,n,1); x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); Update(w[x],w[y],v,1,n,1);//与边修改不同}int main(){ //freopen("in.txt","r",stdin); int m,p,u,v,c; while(scanf("%d%d%d",&n,&m,&p)!=EOF) { memset(son,-1,sizeof(son)); for(int i=0;i<=n;i++) G[i].clear(); cnt=0; for(int i=1;i<=n;i++) scanf("%d",&camp[i]); for(int i=1;i<=m;i++) { scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); } dfs1(1,1,1); dfs2(1,1); Build(1,n,1); char cmd[10]; for(int i=1;i<=p;i++) { scanf("%s",&cmd); if(cmd[0]==‘I‘) { scanf("%d%d%d",&u,&v,&c); Change(u,v,c); } if(cmd[0]==‘D‘) { scanf("%d%d%d",&u,&v,&c); Change(u,v,-c); } if(cmd[0]==‘Q‘) { scanf("%d",&c); printf("%d\n",Query(w[c],1,n,1)); } } }}
| 11757337 | 2014-09-29 16:51:29 | Accepted | 3966 | 2484MS | 8308K | 3299 B | C++ | Physcal |
HDU 3966（树链剖分+点修改+点查询）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。