ural1890 Money out of Thin Air

Money out of Thin Air

Time limit: 1.0 second
Memory limit: 64 MB

Each employee of the company Oceanic Airlines, except for the director, has exactly one immediate superior. To encourage the best employees and best departments, the director can issue two kinds of orders:

“employee x y z” — if the salary of employee x is less than y dollars, increase it by zdollars;
“department x y z” — if the average salary in the department headed by employee x is less than y dollars, increase the salary of each employee at this department by z dollars (the department includes employee x and all her subordinates, not necessarily immediate).

Given the salaries of all the employees of Oceanic Airlines at the beginning of a year and all the salary increase orders issued by the director during the year, find the salaries of the employees by the end of the year. You may assume that the company didn't hire any new employees and didn't fire anyone during the year.

Input

The first line contains integers n, q, and s0, which are the number of employees at Oceanic Airlines, the number of salary increase orders, and the director's salary at the beginning of the year (1 ≤ n, q ≤ 50 000; 0 ≤ s0 ≤ 109). The employees are numbered from 0 to n − 1; the director's number is zero. In the ith of the following n − 1 lines you are given integers piand si, which are the number of the immediate superior and the salary at the beginning of the year of the employee with number i (0 ≤ pi ≤ i − 1; 0 ≤ si ≤ 109). The following q lines are the director's orders given chronologically. Each order has the form “employee x y z” or “department x y z” (the notation x, y, z is explained above), where 0 ≤ x ≤ n − 1 and 1 ≤ y, z ≤ 109.

Output

Output the salaries of all employees at Oceanic Airlines at the end of the year in the ascending order of the employees' numbers.

Sample

input	output
4 3 1 0 10 0 10 1 10 employee 2 15 1 employee 3 5 1 department 0 10 1	2 11 12 11

分析：关键是对员工的原标号进行先序遍历后重新标号，这样每个员工所领导的部门就是一个连续的区间；

　　　然后线段树进行区间修改，注意输出答案再把新标号代回原标号；

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <hash_map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=1e5+10;
const int dis[][2]={0,1,-1,0,0,-1,1,0};
using namespace std;
using namespace __gnu_cxx;
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p%mod;p=p*p%mod;q>>=1;}return f;}
int n,m,k,t,h[maxn],c[maxn],id[maxn],idx[maxn],tot,now,l[maxn],r[maxn];
struct Node
{
    ll sum, lazy;
} T[maxn<<2];

void PushUp(int rt)
{
    T[rt].sum = T[rt<<1].sum + T[rt<<1|1].sum;
}

void PushDown(int L, int R, int rt)
{
    int mid = (L + R) >> 1;
    ll t = T[rt].lazy;
    T[rt<<1].sum += t * (mid - L + 1);
    T[rt<<1|1].sum += t * (R - mid);
    T[rt<<1].lazy += t;
    T[rt<<1|1].lazy += t;
    T[rt].lazy = 0;
}

void Build(int L, int R, int rt)
{
    if(L == R)
    {
        T[rt].sum=c[idx[now++]];
        return ;
    }
    int mid = (L + R) >> 1;
    Build(Lson);
    Build(Rson);
    PushUp(rt);
}

void Update(int l, int r, ll v, int L, int R, int rt)
{
    if(l==L && r==R)
    {
        T[rt].lazy += v;
        T[rt].sum += v * (R - L + 1);
        return ;
    }
    int mid = (L + R) >> 1;
    if(T[rt].lazy) PushDown(L, R, rt);
    if(r <= mid) Update(l, r, v, Lson);
    else if(l > mid) Update(l, r, v, Rson);
    else
    {
        Update(l, mid, v, Lson);
        Update(mid+1, r, v, Rson);
    }
    PushUp(rt);
}

ll Query(int l, int r, int L, int R, int rt)
{
    if(l==L && r== R)
    {
        return T[rt].sum;
    }
    int mid = (L + R) >> 1;
    if(T[rt].lazy) PushDown(L, R, rt);
    if(r <= mid) return Query(l, r, Lson);
    else if(l > mid) return Query(l, r, Rson);
    return Query(l, mid, Lson) + Query(mid + 1, r, Rson);
}
struct node1
{
    int to,nxt;
}p[maxn];
struct node2
{
    char p[10];
    int x,y,z;
}q[maxn];
void add(int x,int y)
{
    tot++;
    p[tot].to=y;
    p[tot].nxt=h[x];
    h[x]=tot;
}
void dfs(int u)
{
    id[u]=++now;
    idx[now]=u;
    l[u]=now;
    for(int i=h[u];i;i=p[i].nxt)
    {
        dfs(p[i].to);
    }
    r[u]=now;
    return;
}
int main()
{
    int i,j;
    scanf("%d%d%d",&n,&m,&c[1]);
    rep(i,2,n)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        a++;
        add(a,i);
        c[i]=b;
    }
    rep(i,1,m)scanf("%s%d%d%d",q[i].p,&q[i].x,&q[i].y,&q[i].z),q[i].x++;
    dfs(1);
    now=1;
    Build(1,n,1);
    rep(i,1,m)
    {
        if(q[i].p[0]=='e')
        {
            if(Query(id[q[i].x],id[q[i].x],1,n,1)<q[i].y)
                Update(id[q[i].x],id[q[i].x],q[i].z,1,n,1);
        }
        else
        {
            if((double)Query(l[q[i].x],r[q[i].x],1,n,1)/(r[q[i].x]-l[q[i].x]+1)<q[i].y)
                Update(l[q[i].x],r[q[i].x],q[i].z,1,n,1);
        }
    }
    rep(i,1,n)printf("%lld
",Query(id[i],id[i],1,n,1));
    //system("Pause");
    return 0;
}