HackerEarth Operations and tree problem solution

In this HackerEarth Operations and tree problem solution Yuqi has an rooted indexed tree T of N nodes indexed from 1 to N. The node 1 is the root. Now on each node there is a value Vi.

He can cast several kinds of magic:

Magic Kind 1: given a,b increase the value in the subtree of node a by b. ( 1 <= a <= N, 0 <= |b| <= 10^9)

Magic Kind 2: given a,b increase the value of node a by b (1 <= a <= N, 0 <= |b| <= 10^9)

Magic Kind 3: given a if a is in the Blacklist remove it, otherwise add it into the blacklist. (1 <= a <= N)

Magic Kind 4: given a.tell Yuqi the value of node a. (1 <= a <= N)

Nodes in Blacklist’s value will not be affected by any other magic until it’s removed.

Now he gives you the list of magic to proceed. You need to proceed them in order. Note that value of any node can be negative at any moment.

HackerEarth Operations and tree problem solution.

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <deque>
#include <bits/stdc++.h>
//#include "testlib.h"
using namespace std;
#define ll long long
#define pii pair<int,int>
#define qi ios::sync_with_stdio(0)

bool debug=true;

template<typename T1,typename T2>ostream& operator<<(ostream& os,pair<T1,T2> ptt){
    os<<ptt.first<<","<<ptt.second;
    return os;
}
template<typename T>ostream& operator<<(ostream& os,vector<T> vt){
    os<<"{";
    for(int i=0;i<vt.size();i++){
        os<<vt[i]<<" ";
    }
    os<<"}";
    return os;
}

int n,q;
vector<int> nei[100005];

int v[100005];

int ts;
int stamp[100005];
int ste[100005];

void dfs(int pos,int fa){
    ts++;
    stamp[pos]=ts;
    for(int to:nei[pos]){
        if(to==fa){
            continue;
        }
        dfs(to,pos);
    }
}

int rq(int pos,int fa){
    int last=stamp[pos];
    for(int to:nei[pos]){
        if(to==fa){
            continue;
        }
        last=max(last,rq(to,pos));
    }
    
    ste[pos]=last;
    return last;
}

struct node{
        ll l,r,lazy,sum;
};

struct Seg{
    node tree[100005*4];
    
    inline void pushup(ll k){
        tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;
    }
    
    inline void pushdown(ll k){
        if(tree[k].lazy){
            tree[k*2].sum+=(tree[k*2].r-tree[k*2].l+1)*tree[k].lazy; 
            tree[k*2+1].sum+=(tree[k*2+1].r-tree[k*2+1].l+1)*tree[k].lazy;
            tree[k*2].lazy+=tree[k].lazy;
            tree[k*2+1].lazy+=tree[k].lazy;
            
            tree[k].lazy=0;
        }
    }
    
    void build(ll l,ll r,ll k){
        tree[k].l=l;
        tree[k].r=r;
        tree[k].lazy=0;
        if(l==r){
            tree[k].sum=0;
//          cin>>tree[k].sum;
            return;
        }
        ll mid=(l+r)/2;
        build(l,mid,k*2);
        build(mid+1,r,k*2+1);
        pushup(k); 
    }
    
    void update(ll l,ll r,ll val,ll k){
        if(l<=tree[k].l && r>=tree[k].r){
            tree[k].sum+=(tree[k].r-tree[k].l+1)*val;
            tree[k].lazy+=val;  
            return;
        }
        pushdown(k); 
        
        ll mid=(tree[k].l+tree[k].r)/2;
        if(l<=mid){
            update(l,r,val,k*2);
        }
        if(r>mid){
            update(l,r,val,k*2+1);
        }   
        
        pushup(k); 
    }
    
    ll query(ll l,ll r,ll k){
        if(l<=tree[k].l && r>=tree[k].r){
            return tree[k].sum;
        }
        
        pushdown(k);
        
        ll mid=(tree[k].l+tree[k].r)/2;
        ll ans=0;
        if(l<=mid){
            ans+=query(l,r,k*2); 
        }
        if(r>mid){
            ans+=query(l,r,k*2+1);
        }
        
        return ans;
    } 
};

Seg tmp,old;

int main(int argc,char* argv[]){
    qi;
    cin>>n;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        nei[a].push_back(b);
        nei[b].push_back(a);
    }
    
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    
    dfs(0,-1);
    rq(0,-1);
    
    old.build(1,n,1);
    tmp.build(1,n,1);
    
    for(int i=0;i<n;i++){
        old.update(stamp[i],stamp[i],v[i],1);
    }
    
    cin>>q;
    set<int> bl;
    
    for(int i=0;i<q;i++){
        int ma;
        cin>>ma;
        if(ma==1){
            int a,b;
            cin>>a>>b;
            a--;
            tmp.update(stamp[a],ste[a],b,1);
        }
        if(ma==2){
            int a,b;
            cin>>a>>b;
            a--;
            tmp.update(stamp[a],stamp[a],b,1);
        }
        if(ma==3){
            int a;
            cin>>a;
            a--;
            if(bl.count(a)){
                tmp.update(stamp[a],stamp[a],-tmp.query(stamp[a],stamp[a],1),1);
                bl.erase(a);
            }else{
                old.update(stamp[a],stamp[a],tmp.query(stamp[a],stamp[a],1),1);
                tmp.update(stamp[a],stamp[a],-tmp.query(stamp[a],stamp[a],1),1);
                bl.insert(a);
            }
        }
        if(ma==4){
            int a;
            cin>>a;
            a--;
            if(bl.count(a)){
                tmp.update(stamp[a],stamp[a],-tmp.query(stamp[a],stamp[a],1),1);
                bl.erase(a);
            }else{
                old.update(stamp[a],stamp[a],tmp.query(stamp[a],stamp[a],1),1);
                tmp.update(stamp[a],stamp[a],-tmp.query(stamp[a],stamp[a],1),1);
                bl.insert(a);
            }
            cout<<old.query(stamp[a],stamp[a],1)<<endl;
        }
    }
    return 0;
}

HackerEarth Operations and tree problem solution

HackerEarth Operations and tree problem solution.

Leave a Reply

Pages

Practice