[BZOJ4756] [Usaco2017 Jan]Promotion Counting（线段树合并）

传送门

此题很有意思，有多种解法

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）

下一篇：[BZOJ3339] Rmq Problem（线段树）

---

线段树 线段树合并