hdu3966_树链剖分

最近在强化知识点深度,发现树链剖分不是很会写了。

回顾一下修改操作:

若两个点在同一条链上,则直接修改这段区间。

若不在同一条链上,修改深度较大的点到其链顶端的区间,同时将这个点变为他所在链顶端的父亲,循环操作直到这两个点在同一条链上,就可以用上一种方法了。

没有用LCA写是因为以前被坑过,不但没有这种方法好写,效率也不太让人满意。

主要是对第二种情况如何写有所遗忘,写道模版再给自己提个醒。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 50005
int n,m,q;
vector<int> map[MAXN];
int size[MAXN],fa[MAXN],son[MAXN],val[MAXN],tid[MAXN],_tid[MAXN],dep[MAXN],top[MAXN];
int cnt;
struct node
{
    int l,r,val;
}tree[MAXN<<2];
void dfs1(int s,int f,int d)
{
    size[s]=1;
    fa[s]=f;
    dep[s]=d;
    int len=map[s].size();
    for(int i=0;i<len;i++)
    {
        int e=map[s][i];
        if(e==f)continue;
        dfs1(e,s,d+1);
        size[s]+=size[e];
        if(son[s]==0)
        son[s]=e;
        else if(size[son[s]]<size[e])
        son[s]=e;
    }
}
void dfs2(int s,int t)
{
    tid[s]=++cnt;
    _tid[cnt]=s;
    top[s]=t;
    if(son[s]!=0)
    dfs2(son[s],t);
    int len=map[s].size();
    for(int i=0;i<len;i++)
    {
        int e=map[s][i];
        if(e!=fa[s] && e!=son[s])
        dfs2(e,e);
    }
}
void build(int l,int r,int now)
{
    tree[now].l=l;
    tree[now].r=r;
    tree[now].val=0;
    if(l==r)
    {
        tree[now].val=val[_tid[l]];
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,now<<1);
    build(mid+1,r,now<<1|1);
}
void down(int now)
{
    tree[now<<1].val+=tree[now].val;
    tree[now<<1|1].val+=tree[now].val;
    tree[now].val=0;
}
void update(int l,int r,int now,int num)
{
    if(l==tree[now].l && r==tree[now].r)
    {
        tree[now].val+=num;
        return ;
    }
    if(tree[now].val)
    down(now);
    int mid=(tree[now].l+tree[now].r)>>1;
    if(r<=mid)
    update(l,r,now<<1,num);
    else if(l>mid)
    update(l,r,now<<1|1,num);
    else
    {
        update(l,mid,now<<1,num);
        update(mid+1,r,now<<1|1,num);
    }
}
void change(int s,int e,int num)
{
    while(top[s]!=top[e])
    {
        if(dep[top[s]]<dep[top[e]])
        swap(s,e);
        update(tid[top[s]],tid[s],1,num);
        s=fa[top[s]];
    }
    if(dep[s]>dep[e])
    swap(s,e);
    update(tid[s],tid[e],1,num);
}
int query(int l,int now)
{
    if(tree[now].l==l && tree[now].r==l)
    return tree[now].val;
    if(tree[now].val)
    down(now);
    int mid=(tree[now].l+tree[now].r)>>1;
    if(l<=mid)
    return query(l,now<<1);
    else
    return query(l,now<<1|1);
}
int main()
{
    while(cin>>n>>m>>q)
    {
        memset(size,0,sizeof(size));
        memset(fa,0,sizeof(fa));
        memset(tid,0,sizeof(tid));
        memset(son,0,sizeof(son));
        cnt=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&val[i]);
            map[i].clear();
        }
        for(int i=1;i<n;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            map[a].push_back(b);
            map[b].push_back(a);
        }
        dfs1(1,-1,1);
        dfs2(1,1);
        build(1,n,1);
        while(q--)
        {
            char ch[5];
            int a,b,c;
            scanf("%s",ch);
            if(ch[0]=='Q')
            {
                scanf("%d",&a);
                printf("%d\n",query(tid[a],1));
            }
            else
            {
                scanf("%d%d%d",&a,&b,&c);
                if(ch[0]=='I')
                change(a,b,c);
                else
                change(a,b,-c);
            }
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

BZOJ1101: [POI2007]Zap(莫比乌斯反演)

Description   FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a ,y<=b,并且gc...

37950
来自专栏数据结构与算法

2017.5.13阶段模拟考试

预计分数:100+50(其实感觉自己写的对)+100 实际分数:100+0+100 P1149 火柴棒等式 题目描述 给你n根火柴棍,你可以拼出多少个形如“A+...

35760
来自专栏owent

PKU POJ 2728 Desert King 解题报告

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=2728

8830
来自专栏数据结构与算法

BZOJ4919: [Lydsy1706月赛]大根堆(set启发式合并)

不是链的时候直接当链做,每个节点维护一个multiset表示计算LIS过程中的单调栈

19310
来自专栏数据结构与算法

LOJ#2552. 「CTSC2018」假面(期望 背包)

转移的时候若要淦这个人,那么\(f[i][j] = (f[i - 1][j] + 1) * p + (f[i - 1][j]) * (1 - p)\)

16040
来自专栏数据结构与算法

2017.10.27涩会题大乱斗部分题解

A  P3741 honoka的键盘 和昨天的T1一样, 枚举改哪一个 1 #include<cstdio> 2 #include<cstring> 3 ...

38670
来自专栏ACM小冰成长之路

POJ-3866-Exclusive Access 2

ACM模版 描述 ? ? ? 题解 这绝对是我做过最长的题,也是最难理解的题,翻译成中文都很难理解。 简单的说,就是安排任务使用两个资源的顺序,使最坏情况下,执...

19780
来自专栏数据结构与算法

186. [USACO Oct08] 牧场旅行

157. [USACO Nov07] 奶牛跨栏 186. [USACO Oct08] 牧场旅行 ★★   输入文件:pwalk.in   输出文件:pwalk....

369100
来自专栏数据结构与算法

Day4上午解题报告

预计分数:50 +0+0=50 实际分数:50+0+10=60 毒瘤出题人,T3不给暴力分 (*  ̄︿ ̄)  T1 https://www.luogu.org/...

28140
来自专栏数据结构与算法

BZOJ1576: [Usaco2009 Jan]安全路经Travel(最短路 并查集)

给你一张无向图,保证从1号点到每个点的最短路唯一。对于每个点求出删掉号点到它的最短路上的最后一条边(就是这条路径上与他自己相连的那条边)后1号点到它的最短路的长...

8410

扫码关注云+社区

领取腾讯云代金券