【dfs+线段树get/set】编程之美 tree

现在的位置: 首页 > 综合 > 正文

RSS

【dfs+线段树get/set】编程之美 tree

2018年04月12日 ⁄ 综合 ⁄ 共 2393字 ⁄ 字号小中大 ⁄ 评论关闭

题目2 : 树

时间限制:4000ms

单点时限:2000ms

内存限制:256MB

描述

有一个N个节点的树，其中点1是根。初始点权值都是0。

一个节点的深度定义为其父节点的深度+1,。特别的，根节点的深度定义为1。

现在需要支持一系列以下操作：给节点u的子树中，深度在l和r之间的节点的权值（这里的深度依然从整个树的根节点开始计算），都加上一个数delta。

问完成所有操作后，各节点的权值是多少。

为了减少巨大输出带来的开销，假设完成所有操作后，各节点的权值是answer[1..N]，请你按照如下方式计算出一个Hash值（请选择合适的数据类型，注意避免溢出的情况）。最终只需要输出这个Hash值即可。

MOD =1000000007; // 10^9 + 7

MAGIC= 12347;

Hash =0;

For i= 1 to N do

Hash = (Hash * MAGIC + answer[i]) mod MOD;

EndFor

输入

第一行一个整数T (1 ≤ T ≤ 5)，表示数据组数。

接下来是T组输入数据，测试数据之间没有空行。

每组数据格式如下：

第一行一个整数N (1 ≤ N ≤ 105)，表示树的节点总数。

接下来N - 1行，每行1个数，a (1 ≤ a ≤ N)，依次表示2..N节点的父亲节点的编号。

接下来一个整数Q(1 ≤ Q ≤ 105)，表示操作总数。

接下来Q行，每行4个整数，u, l, r, delta (1 ≤ u ≤ N, 1 ≤ l ≤ r ≤ N, -109 ≤ delta ≤ 109)，代表一次操作。

输出

对每组数据，先输出一行“Case x: ”，x表示是第几组数据，然后接这组数据答案的Hash值。

数据范围

小数据：1 ≤ N, Q ≤ 1000

大数据：1 ≤ N, Q ≤ 105

样例解释

点1的子树中有1,2,3三个节点。其中深度在2-3之间的是点2和点3。

点2的子树中有2,3两个节点。其中没有深度为1的节点。

所以，执行完所有操作之后，只有2,3两点的权值增加了1。即答案是0 1 1。再计算对应的Hash值即可。

样例输入

样例输出

Case 1: 12348

//代码未经过验证，应该存在bug

#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
#define MOD 1000000007 // 10^9 + 7
#define MAGIC 12347
struct node{
   long long int delta;
}nodes[40000];

int L=1,R=-1;//root-node


void set(int a,int b, int i, int l, int r, int delta){
   while(true){
     if(l>=a&&r<=b) {
       nodes[i].delta+=delta;
       return;
     }
     int mid=(l+r)/2;
     if(b<=mid)  { r=mid;i=i*2+1;}
     else if(a>mid){ l=mid+1;i=i*2+2;}
     else{
       set(a,mid,i*2+1,l,mid,delta);
       set(mid+1,b,i*2+2,mid+1,r,delta);
       return;
     }
   }
}
long long int get(int idx){
    int i=0,l=L,r=R;
    if(idx<l||idx>r) return 0;
    long long int res=nodes[i].delta;
    while(l!=r) {
        int mid=(l+r)/2;
        if(idx<=mid) r=mid,i=i*2+1,res+=nodes[i].delta;
        else l=mid+1,i=i*2+2,res+=nodes[i].delta;
    }
    return res;
}
struct seg{
    int l,r,delta;
    seg(int a,int b,int c):l(a),r(b),delta(c){}
};
void dfs(vector<vector<seg> > &segs,vector<vector<int> > &tree,
        long long int &hash,int depth, int u){
    
    for(int i=0;i<segs[u].size();i++){
        seg &s=segs[u][i];
        set(s.l,s.r,0,L,R,s.delta);
    }
    long long int v=get(depth);
    hash=(hash * MAGIC + v) % MOD;
    
    for(int i=0;i<tree[u].size();i++){
        int v=tree[u][i];
        dfs(segs,tree,hash,depth+1,v);
    }
    ///@error: pop back
    for(int i=0;i<segs[u].size();i++){
        seg &s=segs[u][i];
        set(s.l,s.r,0,L,R,0-s.delta);
    }

}

int main(){
    int N;cin>>N;
    for(int casei=0;casei<N;casei++){

        memset(nodes,0,sizeof(nodes));

        int n;cin>>n;
        vector<vector<int> >tree(n,vector<int>());
        vector<vector<seg> > segs(n,vector<seg>());
        for(int i=1;i<n;i++){
            int a;cin>>a;
            tree[a-1].push_back(i);
        }
        int m;cin>>m;
        for(int i=0;i<m;i++){
            int u,l,r,delta;cin>>u>>l>>r>>delta;
            segs[u-1].push_back(seg(l,r,delta));
        }
        R=n;
        long long int hash=0;
        dfs(segs,tree,hash,1,0);//depth=1
        cout<<"Case "<<casei+1<<": "<<hash<<endl;
    }
    return 0;
}

【上篇】hdu2665 可持续化线段树
【下篇】离散化压缩线段树

作者: lucerne

该日志由 lucerne 于6年前发表在综合分类下，最后更新于 2018年04月12日.
转载请注明: 【dfs+线段树get/set】编程之美 tree | 学步园 +复制链接

抱歉!评论已关闭.

学步园