题目链接：
URAL 1890 . Money out of Thin Air
题目描述：
给出一个公司里面上司和下级的附属关系，还有每一个人的工资，然后有两种询问：
1:employee x y z ，如果编号为x的员工如果工资小于y，就给他加薪z。
2:department x y z ，如果编号为x的员工所管辖的范围内(包括自己)，所有员工的工资平均数小于y，给该范围加薪z。
问q次操作后这个公司内每个员工的工资为多少？
解题思路：
根据上司和下级的附属关系，可以先建一个有向图，然后对有向图进行dfs，求出每个点的dfs序列，根据序列建线段树，对于每个操作，先判断操作区间内是否需要加薪，如果需要就进行加薪操作。HINT！！！！：判定和加薪操作一定要分开，要不然会出错，比如说在一段整体不需要加薪的区间内，在线段树上，有可能前半段需要加薪，但是后半部分员工的薪水比较高。
写代码+debug 花费了两个小时，为什么不够熟练，GG！
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; typedef __int64 LL;
#define lson root*2
#define rson root*2+1
const int maxn = ;
const LL INF = 1e9+; struct node
{
int to, next;
} edge[maxn*];
struct Node
{
int l, r;
LL sum, val;
int len()
{
return (r - l + );
}
int mid ()
{
return (l + r) / ;
}
} tree[maxn*];
int head[maxn], stime[maxn], etime[maxn];
int tot, Max, df[maxn];
LL ans[maxn], w[maxn]; void add (int from, int to)
{
edge[tot].to = to;
edge[tot].next = head[from];
head[from] = tot ++;
}
void dfs (int u)
{
stime[u] = ++ Max;
df[Max] = u; for (int i=head[u]; i!=-; i=edge[i].next)
{
int v = edge[i].to;
dfs (v);
etime[v] = Max;
}
}
void build (int root, int l, int r)
{
tree[root].l = l;
tree[root].r = r;
tree[root].val = ; if (l == r)
{
tree[root].sum = w[df[l]];
return ;
} build (lson, l, tree[root].mid());
build (rson, tree[root].mid()+, r);
tree[root].sum = tree[lson].sum + tree[rson].sum;
} void pushdown (int root)
{
if (tree[root].val == || tree[root].len() == )
return ;
tree[lson].sum += tree[lson].len() * tree[root].val;
tree[rson].sum += tree[rson].len() * tree[root].val;
tree[lson].val += tree[root].val;
tree[rson].val += tree[root].val;
tree[root].val = ;
} LL query (int root, int l, int r)
{
if (tree[root].l == l && tree[root].r == r)
return tree[root].sum; pushdown (root); if (tree[root].mid() >= r)
return query (lson, l, r);
else if (tree[root].mid() < l)
return query (rson, l, r);
else
{
LL num = ;
num += query (lson, l, tree[root].mid());
num += query (rson, tree[root].mid()+, r);
return num;
}
}
void updata (int root, int l, int r, LL x)
{
if (tree[root].l == l && tree[root].r == r)
{
tree[root].sum += tree[root].len() * x;
tree[root].val += x;
return ;
} pushdown (root); if (tree[root].mid() >= r)
updata (lson, l, r, x);
else if (tree[root].mid() < l)
updata (rson, l, r, x);
else
{
updata (lson, l, tree[root].mid(), x);
updata (rson, tree[root].mid()+, r, x);
} tree[root].sum = tree[lson].sum + tree[rson].sum;
}
void display (int root)
{
if (tree[root].l == tree[root].r)
{
int num = tree[root].l;
ans[df[num]] = tree[root].sum;
return ;
} pushdown (root);
display (lson);
display (rson);
} int main ()
{
int n, q; while (scanf ("%d %d %I64d", &n, &q, &w[]) != EOF)
{
memset (head, -, sizeof(head));
memset (df, , sizeof(df));
memset (etime, , sizeof(etime));
tot = Max = ; for (int i=; i<n; i++)
{
int u;
scanf ("%d %I64d", &u, &w[i]);
add (u, i);
} dfs ();
etime[] = Max;
build (, , n); char str[];
LL x, y, z; while (q --)
{
scanf ("%s %I64d %I64d %I64d", str, &x, &y, &z);
if (strcmp (str, "employee") == )
{
LL tmp = query (, stime[x], stime[x]);
if (tmp < y)
updata(, stime[x], stime[x], z);
}
else
{
LL tmp = query (, stime[x], etime[x]);
LL num = (etime[x] - stime[x] + ) * y;
if (tmp < num)
updata(, stime[x], etime[x], z);
}
} display (); for (int i=; i<n; i++)
printf ("%I64d\n", ans[i]);
}
return ;
}