ACM-ICPC 2018 焦作赛区网络预赛 E Jiu Yuan Wants to Eat (树链剖分+线段树）

题目链接：https://nanti.jisuanke.com/t/31714

题意：给你一棵树，初始全为0，有四种操作：

1.u-v乘x 2.u-v加x 3. u-v取反 4.询问u-v的和

思路：

除去第三个操作就是很简单的树链剖分+线段树多重标记下放，所以我们只要考虑怎么维护第三个操作就好了，

由题目给的取反可知：！x = (2^64-1) - x; 但是这样维护还是很麻烦，因为这道题是对2^64取模的,我们可以

尝试把这个式子转换成只有加法和乘法的，这样就可以将其和前面两个操作一起维护降低难度。

我们可以想到：（-x）%(2^64) = (2^64-1)*x%(2^64),那么式子就可以转换成：

！x = (2^64-1)*x + (2^64-1) 这样这个式子就只有乘法和加法操作，以及一个常数，然后带入多重标记维护就好了

数组要开 unsigned long long ,题目给的模数也很特殊，2^64, 因为unsigned long long 溢出的时候相当于对2^64

取模，那么我们就不需要取模操作了，直接运算就完事了。

实现代码：

#include<bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

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

#define mid int m = (l + r) >> 1

#define ll  unsigned long long

const ll inf = ;

const int M = 2e5+;

vector<int>g[M];

int n,cnt1,cnt,a[M];

int son[M],fa[M],head[M],siz[M],top[M],dep[M],tid[M];

ll sum[M<<],add[M<<],mul[M<<];

void dfs1(int u,int faz,int deep){

     dep[u] = deep;

     fa[u] = faz;

     siz[u] = ;

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

        int v = g[u][i];

        //cout<<v<<" ";

        if(v != fa[u]){

            dfs1(v,u,deep+);

            siz[u] += siz[v];

            if(son[u] == -||siz[v] > siz[son[u]])

                son[u] = v;

        }

     }

}

void dfs2(int u,int t){

    top[u] = t;

    tid[u] = ++cnt;

    if(son[u] == -) return;

    dfs2(son[u],t);

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

        int v = g[u][i];

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

            dfs2(v,v);

    }

}

void pushup(int rt){

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

}

void pushdown(int m,int rt){

    add[rt<<] = add[rt<<]*mul[rt] + add[rt];

    add[rt<<|] = add[rt<<|]*mul[rt]+add[rt];

    mul[rt<<] = mul[rt<<]*mul[rt];

    mul[rt<<|] = mul[rt<<|]*mul[rt];

    sum[rt<<] = sum[rt<<]*mul[rt] + add[rt]*(m-(m>>));

    sum[rt<<|] = sum[rt<<|]*mul[rt]+add[rt]*(m>>);

    add[rt] = ; mul[rt] = ;

}

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

    add[rt] = ; mul[rt] = ;

    if(l == r){

        sum[rt] = ;

        return;

    }

    mid;

    build(lson); build(rson);

    pushup(rt);

}

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

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

        if(v == ){

            sum[rt] = sum[rt]*c;

            add[rt] = add[rt]*c;

            mul[rt] = mul[rt]*c;

        }

        else if(v == ){

            sum[rt] = sum[rt] + (ll)c*(r-l+);

            add[rt] = add[rt]+c;

        }

        else if(v == ){

            sum[rt] = inf*sum[rt] + (r-l+)*inf;

            add[rt] = add[rt]*inf+inf;

            mul[rt] *= inf;

        }

        return;

    }

    pushdown(r-l+,rt);

    int m = (l + r) >> ;

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

    if(R > m) update(L,R,c,v,rson);

    pushup(rt);

}

ll query(int L,int R,int l,int r,int rt){

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

        return sum[rt];

    }

    mid;

    pushdown(r-l+,rt);

    ll ret = ;

    if(L <= m) ret += query(L,R,lson);

    if(R > m)  ret += query(L,R,rson);

    return ret;

}

void cover(int x,int y,ll c,int v){

    int fx = top[x],fy = top[y];

    while(fx!=fy){

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

       update(tid[fx],tid[x],c,v,,n,);

        x = fa[fx];fx = top[x];

    }

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

    update(tid[y],tid[x],c,v,,n,);

}

ll ask(int x,int y){   //求两结点路径上的权值和

    int fx = top[x],fy = top[y];

    ll ans = ;

    while(fx != fy){

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

        ans += query(tid[fx],tid[x],,n,);

        x = fa[fx]; fx = top[x];

    }

    ans += (dep[x] > dep[y])?query(tid[y],tid[x],,n,):query(tid[x],tid[y],,n,);

    return ans;

}

void init(){

    cnt = cnt1 = ;

    memset(son,-,sizeof(son));

    dep[] = ; fa[] = ; siz[] = ;

}

int main()

{

    int x,q,op,l,r;

    ll c;

    while(scanf("%d",&n)!=EOF){

        init();

       // cout<<inf<<endl;

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

            scanf("%d",&x);

            g[x].push_back(i);

        }

        dfs1(,,);

        dfs2(,);

        build(,n,);

        scanf("%d",&q);

        while(q--){

            scanf("%d",&op);

            if(op == ||op == ){

                scanf("%d%d%llu",&l,&r,&c);

                cover(l,r,c,op);

            }

            else if(op == ){

                scanf("%d%d",&l,&r);

                cover(l,r,,op);

            }

            else {

                scanf("%d%d",&l,&r);

                printf("%llu\n",ask(l,r));

            }

        }

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

            g[i].clear();

    }

    return ;

}

巴特西

ACM-ICPC 2018 焦作赛区网络预赛 E Jiu Yuan Wants to Eat (树链剖分+线段树）

最新文章

热门文章