正文

HDU 3966 Aragorn's Story (树链剖分入门题)

IP云
IP云V管理员/4 阅读
12/02
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

树上路径区间更新，单点查询。

线段树和树状数组都可以用于本题的维护。

线段树： 

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define lson rt<<1

#define rson rt<<1|1

#define Lson l,m,lson

#define Rson m+1,r,rson

#define max(a,b) a>b? a:b

using namespace std;

const int maxn =5e4+;

struct Edge{

    int to,next;

}E[*maxn];

int n,head[maxn],tot;

int cnt,idx,size[maxn],fa[maxn],son[maxn],dep[maxn],top[maxn],id[maxn],rnk[maxn];

int a[maxn];

struct Node{

    int sum,add;

}tree[maxn<<];

void init()

{

    cnt=idx=tot=;

    memset(head,-,sizeof(head));

    dep[]=,fa[]=,size[]=;

    memset(son,,sizeof(son));

}

void AddEdge(int u,int v)

{

    E[tot] = (Edge){v,head[u]};

    head[u]=tot++;

}

void dfs1(int u)

{

    size[u]=;

    for(int i=head[u];~i;i=E[i].next){

        int v=E[i].to;

        if(v!=fa[u]){

            fa[v]=u;

            dep[v]=dep[u]+;

            dfs1(v);

            size[u]+=size[v];

            if(size[son[u]]<size[v]) son[u]=v;

        }

    }

}

void dfs2(int u,int topu)

{

    top[u]= topu;

    id[u] = ++idx;

    rnk[idx] = u;

    if(!son[u]) return;

    dfs2(son[u],top[u]);

    for(int i=head[u];~i;i=E[i].next){

        int v=E[i].to;

        if(v!=fa[u]&&v!=son[u]) dfs2(v,v);

    }

}

void pushup(int rt){  tree[rt].sum = tree[lson].sum + tree[rson].sum; }

void pushdown(int l,int r,int rt){

    if(tree[rt].add){

        tree[lson].add += tree[rt].add;

        tree[rson].add += tree[rt].add;

        int m = (l+r)>>;

        tree[lson].sum += (m-l+)*tree[rt].add;

        tree[rson].sum += (r-m)*tree[rt].add;

        tree[rt].add =;

    }

}

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

{

    tree[rt].add = ;

    if(l==r){

        tree[rt].sum = a[rnk[l]];

        return;

    }

    int m = (l+r)>>;

    build(Lson);

    build(Rson);

    pushup(rt);

}

void update(int L,int R,int v,int l,int r,int rt){

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

        tree[rt].sum +=(r-l+)*v;

        tree[rt].add +=v;

        return ;

    }

    pushdown(l,r,rt);

    int m =(l+r)>>;

    if(L<=m) update(L,R,v,Lson);

    if(R>m) update(L,R,v,Rson);

    pushup(rt);

}

int query(int p,int l,int r,int rt){        //单点更新

    if(l==r) return tree[rt].sum;

    pushdown(l,r,rt);

    int m = (l+r)>>,ans=;

    if(p<=m) ans= query(p,Lson);

    else ans =query(p,Rson);

    pushup(rt);

    return ans;

}

void UPDATE(int u,int v,int w)

{

    while(top[u]!=top[v]){

        if(dep[top[u]]<dep[top[v]]) swap(u,v);

        update(id[top[u]],id[u],w,,n,);

        u = fa[top[u]];

    }

    if(dep[u]>dep[v])swap(u,v);

    update(id[u],id[v],w,,n,);

}

int main()

{

    #ifndef ONLINE_JUDGE

        freopen("in.txt","r",stdin);

        freopen("out.txt","w",stdout);

    #endif

    int m,q,u,v;

    char op[];

    while(scanf("%d%d%d",&n,&m,&q)==){

        init();

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

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

        while(m--){

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

            AddEdge(u,v);

            AddEdge(v,u);

        }

        dfs1();

        dfs2(,);

        build(,n,);

        while(q--){

            scanf("%s",op);

            if(op[]=='Q'){

                scanf("%d",&u);

                printf("%d\n",query(id[u],,n,));

            }

            else{

                int w;

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

                if(op[]=='D') w = -w;

                UPDATE(u,v,w);

            }

        }

    }

    return ;

}

树状数组： 

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define lson rt<<1

#define rson rt<<1|1

#define Lson l,m,lson

#define Rson m+1,r,rson

#define max(a,b) a>b? a:b

using namespace std;

const int maxn =5e4+;

struct Edge{

    int to,next;

}E[*maxn];

int n,head[maxn],tot;

int idx,size[maxn],fa[maxn],son[maxn],dep[maxn],top[maxn],id[maxn],rnk[maxn];

int a[maxn];

struct Node{

    int sum,add;

}tree[maxn<<];

void init()

{

    idx=tot=;

    memset(head,-,sizeof(head));

    dep[]=,fa[]=,size[]=;

    memset(son,,sizeof(son));

}

void AddEdge(int u,int v)

{

    E[tot] = (Edge){v,head[u]};

    head[u]=tot++;

}

void dfs1(int u)

{

    size[u]=;

    for(int i=head[u];~i;i=E[i].next){

        int v=E[i].to;

        if(v!=fa[u]){

            fa[v]=u;

            dep[v]=dep[u]+;

            dfs1(v);

            size[u]+=size[v];

            if(size[son[u]]<size[v]) son[u]=v;

        }

    }

}

void dfs2(int u,int topu)

{

    top[u]= topu;

    id[u] = ++idx;

    rnk[idx] = u;           //建树用

    if(!son[u]) return;

    dfs2(son[u],top[u]);

    for(int i=head[u];~i;i=E[i].next){

        int v=E[i].to;

        if(v!=fa[u]&&v!=son[u]) dfs2(v,v);

    }

}

void pushup(int rt){  tree[rt].sum = max(tree[lson].sum ,tree[rson].sum); }

void pushdown(int l,int r,int rt){

    if(tree[rt].add){

        tree[lson].add += tree[rt].add;

        tree[rson].add += tree[rt].add;

        int m = (l+r)>>;

        tree[lson].sum += (m-l+)*tree[rt].add;

        tree[rson].sum += (r-m)*tree[rt].add;

        tree[rt].add =;

    }

}

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

{

    tree[rt].add = ;

    if(l==r){

        tree[rt].sum = a[rnk[l]];

        return;

    }

    int m = (l+r)>>;

    build(Lson);

    build(Rson);

    pushup(rt);

}

void update(int L,int R,int v,int l,int r,int rt){

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

        tree[rt].sum +=v;

        tree[rt].add +=v;

        return ;

    }

    pushdown(l,r,rt);

    int m =(l+r)>>;

    if(L<=m) update(L,R,v,Lson);

    if(R>m) update(L,R,v,Rson);

    pushup(rt);

}

int query(int p,int l,int r,int rt){        //单点更新

    if(l==r) return tree[rt].sum;

    pushdown(l,r,rt);

    int m = (l+r)>>,ans=;

    if(p<=m) ans= query(p,Lson);

    else ans =query(p,Rson);

    pushup(rt);

    return ans;

}

int bit[maxn];

void add(int pos,int val){

    for(int i=pos;i<=n;i+= i&(-i)) bit[i]+=val;

}

inline int sum(int pos){

    int res=;

    for(int i=pos;i;i-= i&(-i)) res+=bit[i];

    return res;

}

void UPDATE2(int u,int v,int w)                 //树状数组维护

{

    while(top[u]!=top[v]){

        if(dep[top[u]]<dep[top[v]]) swap(u,v);

        add(id[top[u]],w);

        add(id[u]+,-w);

        u = fa[top[u]];

    }

    if(dep[u]>dep[v]) swap(u,v);

    add(id[u],w);

    add(id[v]+,-w);

}

void UPDATE(int u,int v,int w)                  //线段树维护

{

    while(top[u]!=top[v]){

        if(dep[top[u]]<dep[top[v]]) swap(u,v);

        update(id[top[u]],id[u],w,,n,);

        u = fa[top[u]];

    }

    if(dep[u]>dep[v])swap(u,v);

    update(id[u],id[v],w,,n,);

}

int main()

{

    #ifndef ONLINE_JUDGE

        freopen("in.txt","r",stdin);

        freopen("out.txt","w",stdout);

    #endif

    int m,q,u,v;

    char op[];

    while(scanf("%d%d%d",&n,&m,&q)==){

        init();

        for(int i=;i<=n;++i)  scanf("%d",&a[i]);

        while(m--){

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

            AddEdge(u,v);

            AddEdge(v,u);

        }

        dfs1();

        dfs2(,);

        //build(1,n,1);

        memset(bit,,sizeof(bit));

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

            add(id[i],a[i]);

            add(id[i]+,-a[i]);

        }

        while(q--){

            scanf("%s",op);

            if(op[]=='Q'){

                scanf("%d",&u);

                printf("%d\n",sum(id[u]));

                //printf("%d\n",query(id[u],1,n,1));

            }

            else{

                int w;

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

                if(op[]=='D') w = -w;

                UPDATE2(u,v,w);

                //UPDATE(u,v,w);

            }

        }

    }

    return ;

}

相关阅读

目录[+]