传送门
此题很有意思，有多种解法
1.用天天爱跑步的方法，进入子树的时候ansquery，出去子树的时候ans+query，query可以用树状数组或线段树来搞
2.按dfs序建立主席树
3.线段树的合并
前两个都会，于是学习一下线段树的合并。。
道理用文字解释不清。。。直接看代码就能看懂。。
可以脑补出，合并的操作复杂度是logn的，总时间复杂度nlogn
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 100001 int n, m, cnt, size; int head[N], to[N << 1], next[N << 1], root[N], sum[N * 20], ls[N * 20], rs[N * 20], ans[N], a[N], b[N]; inline int read() inline void add(int x, int y) inline void insert(int &now, int l, int r, int x) int mid = (l + r) >> 1; if(x <= mid) insert(ls[now], l, mid, x); else insert(rs[now], mid + 1, r, x); sum[now] = sum[ls[now]] + sum[rs[now]]; } inline void merge(int &x, int y) sum[x] += sum[y]; merge(ls[x], ls[y]); merge(rs[x], rs[y]); } inline int query(int now, int l, int r, int x, int y) inline void dfs(int u) ans[u] = query(root[u], 1, m, a[u] + 1, m); } int main() std::sort(b + 1, b + n + 1); m = std::unique(b + 1, b + n + 1) b 1; for(i = 1; i <= n; i++) a[i] = std::lower_bound(b + 1, b + m + 1, a[i]) b; for(i = 1; i <= n; i++) insert(root[i], 1, m, a[i]); dfs(1); for(i = 1; i <= n; i++) printf("%d\n", ans[i]); return 0; }
上一篇：[BZOJ1575] [Usaco2009 Jan]气象牛Baric（DP）
下一篇：[BZOJ1576] [Usaco2009 Jan]安全路经Travel（堆优化dijk + （并查集 || 树剖））
线段树 线段树合并
