hdu3966 树链剖分+成段更新

给你n个点，m条边，p次操作。n个点相连后是一棵树。每次操作可以是x 到 y 增加 z，或者减z，或者问当前点的值是多少。
可以将树分成链，每个点在线段树上都有自己的点，然后线段树成段更新一下。
#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<queue>

#include<stack>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define INF 99999999

#define ll __int64

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

using namespace std;

const int MAXN = ;

struct node

{

    int to;

    int v;

    int next;

}edge[MAXN*];

int pre[MAXN],ind,top[MAXN],fa[MAXN],son[MAXN],w[MAXN],deq[MAXN],siz[MAXN],fn;

int tree[MAXN<<],mark[MAXN<<];

int n,m,val[MAXN];

void add(int x,int y)

{

    edge[ind].to = y;

    edge[ind].next = pre[x];

    pre[x] = ind++;

}

void dfs1(int rt,int pa,int d)

{

    deq[rt] = d;

    son[rt] = ;

    fa[rt] = pa;

    siz[rt] = ;

    int i;

    for(i=pre[rt]; i!=-; i=edge[i].next){

        int t = edge[i].to;

        if(t != fa[rt]){

            dfs1(t,rt,d+);

            siz[rt] += siz[t];

            if(siz[son[rt]] < siz[t]){

                son[rt] = t;

            }

        }

    }

}

void dfs2(int rt,int tp)

{

    w[rt] = ++fn;

    top[rt] = tp;

    if(son[rt] != )

        dfs2(son[rt], tp);

    for(int i=pre[rt]; i!=-; i=edge[i].next){

        int t = edge[i].to;

        if(t != son[rt] && t != fa[rt]){

            dfs2(t,t);

        }

    }

}

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

{

    tree[rt] = ;

    mark[rt] = ;

    if(l == r)

        return ;

    int m = (l+r)/;

    build(lson);

    build(rson);

}

void pushdown(int rt)

{

    if(mark[rt] != ){

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

        mark[rt<<] += mark[rt];

        tree[rt<<|] += mark[rt];

        tree[rt<<] += mark[rt];

        mark[rt] = ;

    }

}

void Insert(int p,int v,int l,int r,int rt)

{

    if(l == r){

        tree[rt] = v;

        return ;

    }

    int m = (l+r)/;

    if(m >= p){

        Insert(p,v,lson);

    }

    else Insert(p,v,rson);

}

void updata(int L,int R,int v,int l,int r,int rt)

{

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

        mark[rt] += v;

        tree[rt] += v;

        return ;

    }

    pushdown(rt);

    int m = (l+r)/;

    if(m >= L){

        updata(L,R,v,lson);

    }

    if(m < R){

        updata(L,R,v,rson);

    }

}

int query(int p,int l,int r,int rt)

{

    if(l == r){

        return tree[rt];

    }

    pushdown(rt);

    int m = (l+r)/;

    if(m >= p){

        return query(p,lson);

    }

    else {

        return query(p,rson);

    }

}

void updata_all(int x,int y,int z)

{

    while(top[x] != top[y])

    {

        if(deq[top[x]] < deq[top[y]]){

            swap(x,y);

        }

        updata(w[top[x]],w[x],z,,fn,);

        x = fa[top[x]];

    }

    if(deq[x] < deq[y]){

        swap(x,y);

    }

    updata(w[y],w[x],z,,fn,);

}

int main()

{

    int i,j,p;

    while(~scanf("%d%d%d",&n,&m,&p))

    {

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

            scanf("%d",&val[i]);

        }

        ind = ;

        memset(pre,-,sizeof(pre));

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

            int x,y;

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

            add(x,y);

            add(y,x);

        }

        dfs1(,,);

        fn = ;

        dfs2(,);

        build(,n,);

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

            Insert(w[i],val[i],,fn,);

        }

        char s[];

        while(p--)

        {

            scanf("%s",s);

            if(s[] == 'I'){

                int x,y,z;

                scanf("%d%d%d",&x,&y,&z);

                updata_all(x,y,z);

            }

            else if(s[] == 'D'){

                int x,y,z;

                scanf("%d%d%d",&x,&y,&z);

                updata_all(x,y,-z);

            }

            else {

                int x;

                scanf("%d",&x);

                printf("%d\n",query(w[x],,fn,));

            }

        }

    }

}
巴特西

hdu3966 树链剖分+成段更新

最新文章

热门文章
