Codeforces 396C

题意略。

思路：

将树上的节点编好dfs序，然后就可以用树状数组区间修改点查询了。

我们用 lft[v] 和 rht[v]来表示v的子树在dfs序中的左端和右端，这样才方便我们对树状数组的操作。

其实这个题目的问题在于每个点在修改时，修改的值不是一定的，会发生变化。

我是将加上的值和减去的值分开了。

开两个树状数组，一个记录加：在我们进行加操作的时候，加上的值是x + deep[v] * k。

一个记录减：在我们进行减操作的时候，减去的值就是k。

最后在获取答案的时候，ans = sum(v,0) - deep[v] * sum(v,1)。

详见代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 3e5 + ;

const LL mod = 1e9 + ;

int lft[maxn],rht[maxn],n,q,cnt;

LL deep[maxn],BIT[][maxn];

vector<int> graph[maxn];

void dfs(int cur,int d){

    lft[cur] = ++cnt;

    deep[cur] = d;

    for(int i = ;i < graph[cur].size();++i){

        int v = graph[cur][i];

        dfs(v,d + );

    }

    rht[cur] = cnt;

}

int lowbit(int k){

    return (k & -k);

}

void add(int pos,LL val,int idx){

    while(pos <= n){

        BIT[idx][pos] += val;

        BIT[idx][pos] %= mod;

        pos += lowbit(pos);

    }

}

LL sum(int pos,int idx){

    LL ret = ;

    while(pos > ){

        ret += BIT[idx][pos];

        pos -= lowbit(pos);

        ret %= mod;

    }

    return ret;

}

int main(){

    scanf("%d",&n);

    int pi;

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

        scanf("%d",&pi);

        graph[pi].push_back(i);

    }

    dfs(,);

    scanf("%d",&q);

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

        int type;

        scanf("%d",&type);

        if(type == ){

            int v;

            LL x,k;

            scanf("%d%lld%lld",&v,&x,&k);

            LL val = (x + deep[v] * k) % mod;

            add(lft[v],val,);

            add(rht[v] + ,-val,);

            add(lft[v],k,);

            add(rht[v] + ,-k,);

        }

        else{

            int v;

            scanf("%d",&v);

            int pos = lft[v];

            LL part1 = sum(pos,);

            LL part2 = sum(pos,);

            part2 = part2 * deep[v] % mod;

            LL ans = ((part1 - part2) % mod + mod) % mod;

            printf("%lld\n",ans);

        }

    }

    return ;

}

巴特西

Codeforces 396C

最新文章

热门文章