注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

jytnb1的博客

日影斑驳,朽日浮尘;韶光荏苒,逡巡不前。

 
 
 

日志

 
 
关于我

有志者,事竟成,苦心人,天不负。

网易考拉推荐

【bzoj】4034: [HAOI2015]T2  

2015-10-24 20:52:53|  分类: 题解 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
天真的我天真地打了树链剖分,结果鑫鑫却说用dfs序维护一下就可以了,想了想他说的话很对,我的方法不仅代码复杂度比他的高效率也多一只log。哎╮(╯▽╰)╭,我弱嘛。
题目链接:BZOJ4034

4034: [HAOI2015]T2

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 958  Solved: 331
[Submit][Status][Discuss]
Description
有一棵点数为 N 的树,以点 1 为根,且树点有边权。然后有 M 个
操作,分为三种:
操作 1 :把某个节点 x 的点权增加 a 。
操作 2 :把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 :询问某个节点 x 到根的路径中所有点的点权和。
Input
第一行包含两个整数 N, M 。表示点数和操作数。
接下来一行 N 个整数,表示树中节点的初始权值。
接下来 N-1 行每行三个正整数 fr, to , 表示该树中存在一条边 (fr, to) 。
再接下来 M 行,每行分别表示一次操作。其中第一个数表示该操
作的种类( 1-3 ) ,之后接这个操作的参数( x 或者 x a ) 。
Output
 对于每个询问操作,输出该询问的答案。答案之间用换行隔开。
Sample Input
5 5
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3
Sample Output
6
9
13
HINT
 对于 100% 的数据, N,M<=100000 ,且所有输入数据的绝对值都不
会超过 10^6 。
Source
鸣谢bhiaibogf提供
===========================================================================
模板一道,dfs序维护操作2,树链剖分维护操作3。dfs序维护操作3的方法这里不(wo)做(ye)介(bu)绍(hui)。
===========================================================================

#include<cstdio>
using namespace std;
const int N=100100;
int i,j,k,n,m,ch,ff,o,x,a,En,Pn;
long long ans;
int A[N],h[N];
struct point {int fa,sn,sz,dp,fv,tp;} P[N];
struct edge {int s,n;} E[N<<1];
struct tree {long long ad,sm;} T[N<<2];
void R(int &x)
{
ff=x=0;ch=getchar();
while (ch<'0' || '9'<ch) {if (ch=='-') ff=1;ch=getchar();}
while ('0'<=ch && ch<='9') x=x*10+ch-'0',ch=getchar();
if (ff) x=-x;
}
void W(long long x)
{
if (x<0) putchar('-'),x=-x;
if (x>=10) W(x/10);
putchar('0'+x%10);
}
void E_add(int x,int y)
{
En++;E[En].s=y;
E[En].n=h[x];h[x]=En;
En++;E[En].s=x;
E[En].n=h[y];h[y]=En;
}
void dfs1(int x,int F)
{
int ma=0,k;
P[x].dp=P[F].dp+1;P[x].fa=F;P[x].sz=1;
for (int k=h[x];k;k=E[k].n) if (E[k].s!=F)
{
dfs1(E[k].s,x);
P[x].sz+=P[E[k].s].sz;
if (P[E[k].s].sz>ma)
{
ma=P[E[k].s].sz;
P[x].sn=E[k].s;
}
}
}
void dfs2(int x,int F,int tp)
{
P[x].tp=tp;P[x].fv=++Pn;
if (P[x].sn) dfs2(P[x].sn,x,tp);
for (int k=h[x];k;k=E[k].n) if (E[k].s!=P[x].sn && E[k].s!=F) dfs2(E[k].s,x,E[k].s);
}
void up(int k) { T[k].sm=T[k<<1].sm+T[k<<1|1].sm;}
void down(int L,int R,int k)
{
if (T[k].ad)
{
int mid=(L+R)>>1;
T[k<<1].sm+=T[k].ad*(mid-L+1);
T[k<<1].ad+=T[k].ad;
T[k<<1|1].sm+=T[k].ad*(R-mid);
T[k<<1|1].ad+=T[k].ad;
T[k].ad=0;
}
}
void T_add1(int L,int R,int x,int ad,int k)
{
if (L==R)
{
T[k].sm+=ad;
return;
}
down(L,R,k);
int mid=(L+R)>>1;
if (x<=mid) T_add1(L,mid,x,ad,k<<1);
else T_add1(mid+1,R,x,ad,k<<1|1);
up(k);
}
void T_add2(int L,int R,int l,int r,int ad,int k)
{
if (L==l && R==r)
{
T[k].sm+=1ll*ad*(R-L+1);
if (L<R) T[k].ad+=ad;
return;
}
down(L,R,k);
int mid=(L+R)>>1;
if (r<=mid) T_add2(L,mid,l,r,ad,k<<1);
else
{
if (l>mid) T_add2(mid+1,R,l,r,ad,k<<1|1);
else T_add2(L,mid,l,mid,ad,k<<1),T_add2(mid+1,R,mid+1,r,ad,k<<1|1);
}
up(k);
}
long long T_query(int L,int R,int l,int r,int k)
{
if (L==l && R==r) return T[k].sm;
down(L,R,k);
int mid=(L+R)>>1;
if (r<=mid) return T_query(L,mid,l,r,k<<1);
if (l>mid) return T_query(mid+1,R,l,r,k<<1|1);
return T_query(L,mid,l,mid,k<<1)+T_query(mid+1,R,mid+1,r,k<<1|1);
}
int main()
{
R(n);R(m);
for (i=1;i<=n;i++) R(A[i]);
for (i=1;i<n;i++)
{
R(x);R(a);
E_add(x,a);
}
dfs1(1,0);dfs2(1,0,1);
for (i=1;i<=n;i++) T_add1(1,n,P[i].fv,A[i],1);
for (i=1;i<=m;i++)
{
R(o);
if (o==1)
{
R(x);R(a);
T_add1(1,n,P[x].fv,a,1);
}
if (o==2)
{
R(x);R(a);
T_add2(1,n,P[x].fv,P[x].fv+P[x].sz-1,a,1);
}
if (o==3)
{
ans=0;
R(x);
while (P[x].tp!=1)
{
ans+=T_query(1,n,P[P[x].tp].fv,P[x].fv,1);
x=P[P[x].tp].fa;
}
ans+=T_query(1,n,P[1].fv,P[x].fv,1);
W(ans);puts("");
}
}
}


  评论这张
 
阅读(33)| 评论(6)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017