HDU 3974 Assign the task——线段树

HDU 3974 Assign the task——线段树

题意：有一个公司，有n个人，这些人之间的关系是一棵树，公司会安排一些任务给他们， 每次安排至安排一个人，但是他的下属会和他一起做，要求查询当前这个人在做什么工作

思路：一开始不好往线段树那里想，想用线段树的lazy思想直接处理原来的树，但发现更新和查询都没法精确定位，最坏的情况为O（n），会超时，所以考虑如何在更短的时间内更新和查询，这就想到了线段树，可以在O（nlogn）内完成更新和查询

想用线段树解决问题的话首先要把原来的树重建，把做同样工作的人放在一起，这个用一个dfs和一个数组date【】就可以实现，每次dfs到一个点u就date【++cnt】 = u，这样就能保证相同工作的人在一起了。

在dfs的过程中，我们还需要及时得到一个点的所有子节点数，即一个boss的所有员工数，方便更新时根据boss的位置获得更新区间

然后把原来树的节点和date【】做一个映射，一遍根据原来节点的编号的到他在date【】中的位置

线段树维护的是每个叶子的情况，不需要维护区间加法，所以只用一个lazy数组就可以解决问题，具体参考代码

#include #include #include #include #include using namespace std;const int maxn = 5 *1e5 + 10;char c;int T, n, m, a, b, cnt, rudu[maxn], date[maxn], shuliang[maxn], yingshe[maxn];int lazy[maxn<<2];vector tree[maxn];void init() { cnt = 0; memset(rudu, 0, sizeof(rudu)); memset(lazy, -1, sizeof(lazy)); for (int i = 1; i <= n; i++) { tree[i].clear(); }}int dfs(int u) { date[++cnt] = u; if (tree[u].empty()) return shuliang[u] = 0; int temp = 0; for (int i = 0; i < tree[u].size(); i++) { int v = tree[u][i]; temp += dfs(v) + 1; } return shuliang[u] = temp;}void pushdown(int root) { if (lazy[root] != -1) { lazy[root<<1] = lazy[root<<1|1] = lazy[root]; lazy[root] = -1; }}void update_interval(int L, int R, int root, int uL, int uR, int val) { if (uL <= L && R <= uR) { lazy[root] = val; return; } int mid = (L + R)>>1; pushdown(root); if (uL <= mid) { update_interval(L, mid, root<<1, uL, uR, val); } if (uR > mid) { update_interval(mid + 1, R, root<<1|1, uL, uR, val); }}int query(int L, int R, int root, int pos) { if (L == R) { return lazy[root]; } int mid = (L + R)>>1; pushdown(root); if (pos <= mid) { return query(L, mid, root<<1, pos); } else { return query(mid + 1, R, root<<1|1, pos); }}int main(){ scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { scanf("%d", &n); init(); for (int i = 1; i <= n - 1; i++) { scanf("%d %d", &a, &b); tree[b].push_back(a); rudu[a]++; } for (int i = 1; i <= n; i++) { if (!rudu[i]) { dfs(i); break; } } for (int i = 1; i <= n; i++) { yingshe[date[i]] = i; } scanf("%d", &m); printf("Case #%d:\n", kase); while (m--) { cin >> c; if (c == 'T') { scanf("%d %d", &a, &b); update_interval(1, n, 1, yingshe[a], yingshe[a] + shuliang[a], b); } else { scanf("%d", &a); printf("%d\n", query(1, n, 1, yingshe[a])); } } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。