BZOJ2863[SHOI2012]魔法树——树链剖分+线段树-白红宇的个人博客

BZOJ2863[SHOI2012]魔法树——树链剖分+线段树

发布日期：2021-08-27 14:53:43 浏览次数：2 分类：技术文章

本文共 1904 字，大约阅读时间需要 6 分钟。

题目描述

输入

输出

样例输入

0 1

1 2

2 3

Add 1 3 1

Query 0

Query 1

Query 2

样例输出

　　树链剖分模板题，路径修改子树查询，注意节点编号从零开始，答案爆int。

#include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #define ll long longusing namespace std;int n,m;int num;int tot;int ans;int x,y,z;char ch[10];ll a[800010];int s[100010];int t[100010];int d[100010];int f[100010];int to[100010];ll sum[800010];int son[100010];int top[100010];int head[100010];int next[100010];int size[100010];void add(int x,int y){ tot++; next[tot]=head[x]; head[x]=tot; to[tot]=y;}void dfs(int x){ size[x]=1; d[x]=d[f[x]]+1; for(int i=head[x];i;i=next[i]) { dfs(to[i]); size[x]+=size[to[i]]; if(size[to[i]]>size[son[x]]) { son[x]=to[i]; } }}void dfs2(int x,int tp){ s[x]=++num; top[x]=tp; if(son[x]) { dfs2(son[x],tp); } for(int i=head[x];i;i=next[i]) { if(to[i]!=son[x]) { dfs2(to[i],to[i]); } } t[x]=num;}void pushup(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1];}void pushdown(int rt,int l,int r){ if(a[rt]) { int mid=(l+r)>>1; a[rt<<1]+=a[rt]; a[rt<<1|1]+=a[rt]; sum[rt<<1]+=(mid-l+1)*a[rt]; sum[rt<<1|1]+=(r-mid)*a[rt]; a[rt]=0; }}void change(int rt,int l,int r,int L,int R,int v){ if(L<=l&&r<=R) { sum[rt]+=(r-l+1)*v; a[rt]+=v; return ; } pushdown(rt,l,r); int mid=(l+r)>>1; if(L<=mid) { change(rt<<1,l,mid,L,R,v); } if(R>mid) { change(rt<<1|1,mid+1,r,L,R,v); } pushup(rt);}ll query(int rt,int l,int r,int L,int R){ if(L<=l&&r<=R) { return sum[rt]; } pushdown(rt,l,r); int mid=(l+r)>>1; ll res=0; if(L<=mid) { res+=query(rt<<1,l,mid,L,R); } if(R>mid) { res+=query(rt<<1|1,mid+1,r,L,R); } return res;}void lca(int x,int y,int v){ while(top[x]!=top[y]) { if(d[top[x]]
                
                 d[y]) { swap(x,y); } change(1,1,n,s[x],s[y],v);}int main(){ scanf("%d",&n); for(int i=1;i

转载于:https://www.cnblogs.com/Khada-Jhin/p/9622488.html

转载地址：https://blog.csdn.net/weixin_33918357/article/details/92657790 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：BZOJ2084[Poi2010]Antisymmetry——回文自动机

下一篇：Java注释模板

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题目描述

输入

输出

样例输入

样例输出

发表评论

最新留言

关于作者

推荐文章