HDU 5044 （树链剖分+树状数组+点/边改查）

时间：2023-03-08 19:49:57
HDU 5044 （树链剖分+树状数组+点/边改查）

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5044

题目大意：修改链上点，修改链上的边。查询所有点，查询所有边。

解题思路：

2014上海网赛的变态树链剖分模板题。将以往树链剖分的点&边修改和查询合在一起之后，难度上去不少。

第一个卡人点是读入优化。

第二个卡人点是树状数组。由于要查询所有点，如果使用线段树，每次都要扫到底层才能取出点值，必T无疑。

然后使用树状数组之后，树链剖分的点/边修改写法有些变动。

点查询变化不大。

边查询只要查询一下dep(u,v)大的那一端。

具体变化请仔细看代码。

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include "cstdio"

#include "cstring"

#include "iostream"

using namespace std;

#define maxn 100005

template <class T>

inline bool read(T &ret)

{

    char c;

    int sgn;

    if(c=getchar(),c==EOF) return ; //EOF

    while(c!='-'&&(c<''||c>'')) c=getchar();

    sgn=(c=='-')?-:;

    ret=(c=='-')?:(c-'');

    while(c=getchar(),c>=''&&c<='') ret=ret*+(c-'');

    ret*=sgn;

    return ;

}

int s[maxn],dep[maxn],w[maxn],fa[maxn],top[maxn],son[maxn],tol,cnt,n,head[maxn];

struct Edge

{

    int u,v,c;

}edge[maxn];

struct EDGE

{

    int next,to;

}e[*maxn];

void addedge(int u,int v)

{

    e[tol].to=v;

    e[tol].next=head[u];

    head[u]=tol++;

}

void dfs1(int u,int pre,int d)

{

    s[u]=;fa[u]=pre;dep[u]=d;son[u]=-;

    for(int i=head[u];i!=-;i=e[i].next)

    {

        int v=e[i].to;

        if(v==pre) continue;

        dfs1(v,u,d+);

        s[u]+=s[v];

        if(son[u]!=-||s[v]>s[son[u]]) son[u]=v;

    }

}

void dfs2(int u,int tp)

{

    w[u]=++cnt;top[u]=tp;

    if(son[u]!=-) dfs2(son[u],tp);

    for(int i=head[u];i!=-;i=e[i].next)

    {

        int v=e[i].to;

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

    }

}

//Binary-Indexed-Tree type:0-point,1-edge

int psum[maxn],esum[maxn];

inline int lowbit(int x) {return x&(-x);}

int sum(int x,int type)

{

    int ret=;

    while(x>)

    {

        if(!type) ret+=psum[x];

        else ret+=esum[x];

        x-=lowbit(x);

    }

    return ret;

}

void add(int x,int d,int type)

{

    while(x<=n)

    {

        if(!type) psum[x]+=d;

        else esum[x]+=d;

        x+=lowbit(x);

    }

}

void p_Change(int x,int y,int v)

{

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

    {

        if(dep[top[x]]<dep[top[y]]) swap(x,y);

        add(w[top[x]],v,);

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

        x=fa[top[x]];

    }

    if(dep[x]>dep[y]) swap(x,y);

    add(w[x],v,);

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

}

void e_Change(int x,int y,int v)

{

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

    {

        if(dep[top[x]]<dep[top[y]]) swap(x,y);

        add(w[top[x]],v,);

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

        x=fa[top[x]];

    }

    if(dep[x]>dep[y]) swap(x,y);

    if(x!=y) //这个判断非常重要，没有的话T死你

    {

        add(w[son[x]],v,);

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

    }

}

int main()

{

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

    int T,u,v,c,m,no=;

    char cmd[];

    read(T);

    while(T--)

    {

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

        memset(esum,,sizeof(esum));

        memset(psum,,sizeof(psum));

        tol=cnt=;

        read(n);read(m);

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

        {

            read(edge[i].u);read(edge[i].v);

            addedge(edge[i].u,edge[i].v);

            addedge(edge[i].v,edge[i].u);

        }

        dfs1(,,);

        dfs2(,);

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

          if(dep[edge[i].u]<dep[edge[i].v]) swap(edge[i].u,edge[i].v);

        while(m--)

        {

            scanf("%s",cmd);

            read(u);read(v);read(c);

            if(cmd[]=='') p_Change(u,v,c);

            if(cmd[]=='') e_Change(u,v,c);

        }

        printf("Case #%d:\n",++no);

        for(int i=;i<=n;i++) {if(i>=) printf(" ");printf("%d",sum(w[i],));}

        printf("\n");

        for(int i=;i<n;i++) {if(i>=) printf(" ");printf("%d",sum(w[edge[i].u],));}

        printf("\n");

    }

}
11824525 2014-10-08 17:34:00 Accepted 5044 3718MS 11576K 3384 B C++ Physcal

相关文章