hdu|HDU 6133 Army Formations 树状数组 + 启发式合并 hdu|线段树&&BIT&&平方分割

传送门：HDU6133
题意：给你一棵n个节点的二叉树，每个节点要提交一个任务，需要花费一定的时间，每个节点都要提交这个节点和其子树所有的任务，从0时刻开始提交任务，每个任务提交时的罚时定义为该任务提交的时刻 + 该任务提交所需的时间。求每个节点提交完所有任务的最小罚时。
思路：首先结合样例我们可以将题意转化为：对于每个节点，将其子树上所有点按权值从小到大排序，则所求结果为∑val[i] * (n - i)，n为子树总节点数。
【hdu|HDU 6133 Army Formations 树状数组 + 启发式合并】官方题解：

文章图片

结合上面转化的题意，我们就能用树状数组求sumofsum了。
代码：

#include #define ll long long #define inf 0x3f3f3f3f using namespace std; typedef pair P; const int MAXN = 100010; vector g[MAXN]; int lson[MAXN], rson[MAXN], size[MAXN]; int pos[MAXN], a[MAXN], val[MAXN]; ll ans[MAXN], bit_num[MAXN], bit_sum[MAXN]; int sz; ll SUM; void dfs(int u, int fa) { size[u] = 1; for(int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if(v == fa) continue; if(!lson[u]) lson[u] = v; else rson[u] = v; dfs(v, u); size[u] += size[v]; } if(lson[u] && rson[u] && size[lson[u]] > size[rson[u]]) swap(lson[u], rson[u]); } ll query(ll *arr, int i) { ll res = 0; while(i) { res += arr[i]; i -= i & -i; } return res; } void update(ll *arr, int i, int x) { while(i <= sz) { arr[i] += x; i += i & -i; } } void add(int id) { SUM += (query(bit_num, sz) - query(bit_num, id)) * val[id] + val[id]; SUM += query(bit_sum, id); update(bit_num, id, 1); update(bit_sum, id, val[id]); } void del(int id) { update(bit_num, id, -1); update(bit_sum, id, -val[id]); SUM -= (query(bit_num, sz) - query(bit_num, id)) * val[id] + val[id]; SUM -= query(bit_sum, id); } void clr(int u) { del(pos[u]); if(lson[u]) clr(lson[u]); if(rson[u]) clr(rson[u]); } void merge(int u) { add(pos[u]); if(lson[u]) merge(lson[u]); if(rson[u]) merge(rson[u]); } void solve(int u) { if(!lson[u]) { ans[u] = a[u]; add(pos[u]); return ; } solve(lson[u]); if(rson[u]) { clr(lson[u]); solve(rson[u]); merge(lson[u]); } add(pos[u]); ans[u] = SUM; } int main() { int T, n, u, v; cin >> T; while(T--) { SUM = 0; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", a + i), val[i] = a[i]; sort(val + 1, val + n + 1); sz = unique(val + 1, val + n + 1) - val - 1; for(int i = 1; i <= n; i++) { g[i].clear(); bit_sum[i] = bit_num[i] = 0; lson[i] = rson[i] = size[i] = 0; pos[i] = lower_bound(val + 1, val + sz, a[i]) - val; } for(int i = 1; i < n; i++) { scanf("%d %d", &u, &v); g[u].push_back(v); g[v].push_back(u); } dfs(1, -1); solve(1); for(int i = 1; i <= n; i++) printf("%lld ", ans[i]); puts(""); } return 0; }

这题还有线段树合并的解法，就是将每一个节点看成一颗线段树（叶节点也是），然后自底向上的不断合并线段树，动态更新答案，但是由于线段树空间开销比较大，因此这种做法空间上限非常紧，一不小心就会MLE。不过也是一种很好的思路。传送门：点击打开链接点击打开链接