ACM-ICPC 2018 race area network preliminaries E (tree chain split + line segment tree)

Topic link: https://nanti.jisuanke.com/t/A2015

Topic: Give you a tree, the root node is 1, the initial value of each node is 0, support the following operations

1. u v x multiplies the value of each node on the U - > V path by X

2. u v x adds x to every node value on U - > V path

3. u v reverses the value of each node on the U - > V path bit by bit

4. u v Finds the sum of the values of each node on the U - > V path

Analysis: If there is no 3 operations, it is a naked tree dissection problem, but 3 can be obtained by combining addition and multiplication, and X is inverse = all 1 (64 1)-X.

That is to say, the value of X*(-1)+the maximum unsigned long will actually overflow naturally by taking 2 ^ 64 modules.

Ac code:

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull ULLmax=18446744073709551615;
const int maxn=1e5+5;
/// Tree section
int dfn[maxn],dep[maxn],sze[maxn],rk[maxn],son[maxn],fa[maxn],top[maxn];
struct Edge{
    int v,nxt;
}edge[maxn<<1];
int tot,cnt,head[maxn],n;
void init(int n)
{
    tot=0;
    cnt=0;/// dfs serial node number
    memset(head,-1,sizeof head);
    for(int i=0;i<=n;i++) sze[i]=0,dep[i]=0,son[i]=0,dfn[i]=0,rk[i]=0,fa[i]=0,top[i]=0;
    dep[1]=1;
}
void addedge(int u,int v)
{
    edge[tot].v=v;
    edge[tot].nxt=head[u];
    head[u]=tot++;
}
void dfs1(int u,int faa)
{
    sze[u]=1;
    for(int i=head[u];~i;i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(v==faa) continue;
        dep[v]=dep[u]+1;
        fa[v]=u;
        dfs1(v,u);
        sze[u]+=sze[v];
        if(sze[v]>sze[son[u]])
            son[u]=v;
    }
}
void dfs2(int u,int Top)
{
    dfn[u]=++cnt;
    rk[cnt]=u;
    top[u]=Top;
    if(son[u]) dfs2(son[u],Top);
    for(int i=head[u];~i;i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(v!=fa[u]&&v!=son[u])
            dfs2(v,v);
    }
}
/// Segment Tree Section
struct Tree{
    ull sum,lazy1,lazy2;/// lazy 1 is plus and lazy 2 is multiplication
}tree[maxn<<2];
void pushup(int rt)
{
    tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
void pushdown(int rt,int llen,int rlen)
{
    if(tree[rt].lazy2!=1)
    {
        tree[rt<<1].sum*=tree[rt].lazy2;
        tree[rt<<1].lazy2*=tree[rt].lazy2;
        tree[rt<<1].lazy1*=tree[rt].lazy2;

        tree[rt<<1|1].sum*=tree[rt].lazy2;
        tree[rt<<1|1].lazy2*=tree[rt].lazy2;
        tree[rt<<1|1].lazy1*=tree[rt].lazy2;

        tree[rt].lazy2=1;
    }
    if(tree[rt].lazy1)
    {
        tree[rt<<1].sum+=tree[rt].lazy1*llen;
        tree[rt<<1].lazy1+=tree[rt].lazy1;

        tree[rt<<1|1].sum+=tree[rt].lazy1*rlen;
        tree[rt<<1|1].lazy1+=tree[rt].lazy1;
        tree[rt].lazy1=0;
    }
}
void buildtree(int rt,int l,int r)
{
    if(l==r){
        tree[rt].sum=0;
        tree[rt].lazy1=0;
        tree[rt].lazy2=1;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(rt,mid-l+1,r-mid);/// Don't forget, to update the lazy tag, the default lazy is 0, and now lazy is 1.
    buildtree(rt<<1,l,mid);
    buildtree(rt<<1|1,mid+1,r);
    pushup(rt);
}
void update1(int rt,int l,int r,int L,int R,ull val)//Plus
{
    if(L<=l&&r<=R){
        tree[rt].lazy1+=val;
        tree[rt].sum+=val*(r-l+1);
        return;
    }
    int mid=(l+r)>>1;
    pushdown(rt,mid-l+1,r-mid);
    if(mid>=L) update1(rt<<1,l,mid,L,R,val);
    if(mid<R) update1(rt<<1|1,mid+1,r,L,R,val);
    pushup(rt);
}
void update2(int rt,int l,int r,int L,int R,ull val)/// ride
{
    if(L<=l&&r<=R){
        tree[rt].lazy2*=val;
        tree[rt].lazy1*=val;
        tree[rt].sum*=val;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(rt,mid-l+1,r-mid);
    if(mid>=L) update2(rt<<1,l,mid,L,R,val);
    if(mid<R) update2(rt<<1|1,mid+1,r,L,R,val);
    pushup(rt);
}
ull query(int rt,int l,int r,int L,int R)
{
    if(L<=l&&r<=R){
        return tree[rt].sum;
    }
    int mid=(l+r)>>1;
    ull ans=0;
    pushdown(rt,mid-l+1,r-mid);
    if(mid>=L) ans+=query(rt<<1,l,mid,L,R);
    if(mid<R) ans+=query(rt<<1|1,mid+1,r,L,R);
    return ans;
}
void upadd(int u,int v,ull val)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])
           swap(u,v);
        update1(1,1,n,dfn[top[u]],dfn[u],val);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])
        swap(u,v);
    update1(1,1,n,dfn[v],dfn[u],val);
}
void upmul(int u,int v,ull val)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])
            swap(u,v);
        update2(1,1,n,dfn[top[u]],dfn[u],val);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])
        swap(u,v);
    update2(1,1,n,dfn[v],dfn[u],val);
}
ull qsum(int u,int v)
{
    ull ans=0;
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])
            swap(u,v);
        ans+=query(1,1,n,dfn[top[u]],dfn[u]);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])
        swap(u,v);
    ans+=query(1,1,n,dfn[v],dfn[u]);
    return ans;
}
int main()
{
    int m,u,v;
    while(scanf("%d",&n)!=EOF)
    {
        init(n);
        for(int i=2;i<=n;i++)
        {
            scanf("%d",&u);
            addedge(i,u);
            addedge(u,i);
        }
        dfs1(1,-1);
        dfs2(1,1);
        buildtree(1,1,n);
        scanf("%d",&m);
        int op;
        ull x;
        while(m--){
            scanf("%d%d%d",&op,&u,&v);
            if(op==1){
                scanf("%llu",&x);
                upmul(u,v,x);
                ///updatemul();
            }
            else if(op==2){
                scanf("%llu",&x);
                upadd(u,v,x);
                ///updateadd();
            }
            else if(op==3){
                upmul(u,v,-1);
                upadd(u,v,ULLmax);
                ///updatemul(-1)+updateadd(Max)
            }
            else{
                printf("%llu\n",qsum(u,v));
                ///query();
            }
        }
    }
    return 0;
}

 

Posted on Wed, 09 Oct 2019 12:04:56 -0700 by dupreelove