BZOJ4034 [HAOI2015]树上操作+DFS序+线段树

参考：https://www.cnblogs.com/liyinggang/p/5965981.html

题意：是一个数据结构题，树上的，用dfs序，变成线性的；

思路:对于每一个节点x,记录其DFS序,包括第一次到的序号，用in【x】记录，离开的序号out【x】记录，

再开一个数组seg，in：（序号——>节点的值）；out：（序号——>节点的负值）；

这样就可以使得

　　对于树来说：若所求的一个区间完全包含一个不相关子树，这个子树对结果不影响;

　　对于基于线性的线段树来说，同时包含in【x】、out【x】区间，区间求和为0；

利用线段树build 数组seg，得到区间的加和；

所以，

1-->分别更新in【x】，out【x】所对应的值；

2-->update in【x】到out【x】区间的值；

3-->返回 1 （根）到 in【x】区间的即可；

#include <iostream>

#include <cstdio>

#include <vector>

#define pb push_back

using namespace std;

typedef long long ll;

const int maxn = ;

ll sum[maxn*];

ll seg[maxn],a[maxn],lazy[maxn*],flag[maxn*];

ll in[maxn],out[maxn];

ll io[maxn];

int cnt = ;

int n,m;

vector <int> mp[maxn];

void dfs(int u,int fa)

{

    cnt++;

    seg[cnt] = 1ll*a[u],in[u] = 1ll*cnt;

    for(int i=; i< mp[u].size(); i++)

    {

        int tmp  = mp[u][i];

        if(tmp == fa)continue;

        dfs(tmp,u);

    }

    cnt++;

    seg[cnt] = -1ll*a[u],out[u] = 1ll*cnt;

    io[cnt] = -;

}

void pushup(int rt)

{

    sum[rt] = sum[rt<<] + sum[rt<<|];

    flag[rt] = flag[rt<<] + flag[rt<<|];

}

void pushdown(int rt)

{

    if(lazy[rt])

    {

        lazy[rt<<]  += lazy[rt];

        lazy[rt<<|]+= lazy[rt];

        sum[rt<<]   += flag[rt<<] * lazy[rt];

        sum[rt<<|] += flag[rt<<|]*lazy[rt];

        lazy[rt] = ;

    }

}

void build(int rt,int l,int r)

{

    if(l==r)

    {

        sum[rt] = seg[l];

        if(io[l]==)flag[rt] = ;

        else flag[rt] = -;

        return ;

    }

    int mid = (l+r)>>;

    build(rt<<,l,mid);

    build(rt<<|,mid+,r);

    pushup(rt);

}

    void update_one(int pos,int d,int l,int r,int rt)//单点更新；

    {

        if(l == r)

        {

            if(flag[rt] == )

                sum[rt] += d;

            else sum[rt] -= d;

            return;

        }

        pushdown(rt);

        int mid = (l+r)>>;

        if(pos<=mid) update_one(pos,d,l,mid,rt<<);

        else update_one(pos,d,mid+,r,rt<<|);

        pushup(rt);

    }

    void update_d(int L,int R,int d,int l,int r,int rt)//区间更新；

    {

        if(l >= L && R >= r)

        {

            sum[rt] += flag[rt]*d;

            lazy[rt] += d;

            return;

        }

        pushdown(rt);

        int mid = (l+r)>>;

        if(L<=mid) update_d(L,R,d,l,mid,rt<<);

        if(R>mid) update_d(L,R,d,mid+,r,rt<<|);

        pushup(rt);

    }

    ll query(int L,int R,int l,int r,int rt)//区间查询

    {

        if(l>=L&&r<=R)

        {

            return sum[rt];

        }

        int mid = (l+r)>>;

        ll res = ;

        pushdown(rt);

        if(mid>=L)res += query(L,R,l,mid,rt<<);

        if(mid<R)res +=query(L,R,mid+,r,rt<<|);

        return res;

    }

    int main(){

        scanf("%d%d",&n,&m);

        for(int i=; i<=n;i++)

        {

            scanf("%lld" ,&a[i]);

        }

        for(int i=; i<n;i++)

        {

            int u,v;

            scanf("%d%d",&u,&v);

            mp[v].pb(u);

            mp[u].pb(v);

        }

        dfs(,);

        build(,,*n);

        for(int i= ;i <= m; i++)

        {

            int op,x,val;

            scanf("%d", &op);

            if(op==) {

                scanf("%d%d",&x,&val);

                update_one(in[x],val,,*n,);

                update_one(out[x],val,,*n,);

            }

            else if(op==) {

                scanf("%d%d",&x,&val);

                update_d(in[x],out[x],val,,*n,);

            }

            else if(op==) {

                scanf("%d",&x);

                printf("%lld\n",query(,in[x],,*n,));

            }

        }

        return ;

    }

巴特西

BZOJ4034 [HAOI2015]树上操作+DFS序+线段树

最新文章

热门文章