锐客网

  1. 首页 > it技术 > >

图论算法|luogu P3178 [HAOI2015]树上操作

图论算法|luogu P3178 [HAOI2015]树上操作
文章图片

analysis 【图论算法|luogu P3178 [HAOI2015]树上操作】一看题，修改点和链查询子树点集的权值和，就是树链剖分了！
code

#include using namespace std; #define loop(i,start,end) for(register int i=start; i<=end; ++i) #define anti_loop(i,start,end) for(register int i=start; i>=end; --i) #define clean(arry,num) memset(arry,num,sizeof(arry)) #define ll long long #define max(a,b) ((a>b)?a:b) #define min(a,b) ((avoid read(T &x){ x=0; char r=getchar(); T neg=1; while(r<'0'||r>'9'){if(r=='-')neg=-1; r=getchar(); } while(r>='0'&&r<='9'){x=(x<<1)+(x<<3)+r-'0'; r=getchar(); } x*=neg; } inline void addl(int u,int v){ edge[cnt].e=v; edge[cnt].nxt=head[u]; head[u]=cnt++; } void dfs1(int u,int f){ fa[u]=f; dep[u]=dep[f]+1; siz[u]=1; for(int i=head[u]; i!=-1; i=edge[i].nxt){ int v=edge[i].e; if(v==f)continue; dfs1(v,u); siz[u]+=siz[v]; son[u]=((siz[son[u]][v])?v:son[u]); //siz[0]==0 } } void dfs2(int u,int fa){ if(son[u]){ seg[son[u]]=++seg[0]; //seg[u]=++seg[0]; rev[seg[0]]=son[u]; //rev[seg[0]]=u; top[son[u]]=top[u]; dfs2(son[u],u); } for(int i=head[u]; i!=-1; i=edge[i].nxt){ int v=edge[i].e; if(!top[v]){ seg[v]=++seg[0]; rev[seg[0]]=v; top[v]=v; dfs2(v,u); } } } inline void pushdown(int l,int r,int rt){ if(!lazy[rt])return; lazy[rt<<1]+=lazy[rt]; lazy[rt<<1|1]+=lazy[rt]; sum[rt<<1]+=lazy[rt]*(((r+l)>>1)-l+1); //sum[rt<<1|1]+=lazy[rt]*(((r+l)>>1)-l+1); sum[rt<<1|1]+=lazy[rt]*(r-(((l+r)>>1)+1)+1); lazy[rt]=0; } inline void pushup(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void build(int l,int r,int rt){ if(l==r){ sum[rt]=num[rev[l]]; return; } int mid=l+((r-l)>>1); build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); pushup(rt); } ll query(int l,int r,int nl,int nr,int rt){ if(l<=nl&&nr<=r){ return sum[rt]; } pushdown(nl,nr,rt); int mid=(nl+((nr-nl)>>1)); //int mid=(l+((r-l)>>1)); ll _sum=0; if(mid>=l)_sum+=query(l,r,nl,mid,rt<<1); if(mid>1); if(mid>=l)update(l,r,nl,mid,rt<<1,w); if(mid

    推荐阅读


    上一篇：用php搞网页版四则运算

    下一篇：POJ 2411 Mondriaan's Dream【状压DP】