POJ 2104 归并树

链接：

题解：

归并树和普通的线段树的区别就是每个结点存的是一个序列，所以把int改成vector<int> 就可以了

然后就可以调用merge来pushup 用lower_bound或者lower_bound查询

代码：

31 int a[MAXN], num[MAXN];
32 VI tree[MAXN << 2];
33 
34 void pushup(int l, int r, int rt) {
35     tree[rt].resize(r - l + 1);
36     merge(all(tree[rt << 1]), all(tree[rt << 1 | 1]), tree[rt].begin());
37 }
38 
39 void build(int l, int r, int rt) {
40     if (l == r) {
41         tree[rt].pb(a[l]);
42         return;
43     }
44     int m = (l + r) >> 1;
45     build(lson);
46     build(rson);
47     pushup(l, r, rt);
48 }
49 
50 int query(int L, int R, int x, int l, int r, int rt) {
51     if (L <= l && r <= R) return upper_bound(all(tree[rt]), x) - tree[rt].begin();
52     int m = (l + r) >> 1;
53     int ret = 0;
54     if (L <= m) ret += query(L, R, x, lson);
55     if (R > m) ret += query(L, R, x, rson);
56     return ret;
57 }
58 
59 int main() {
60     int n, m;
61     cin >> n >> m;
62     rep(i, 1, n + 1) scanf("%d", a + i), num[i] = a[i];
63     sort(num + 1, num + 1 + n);
64     build(1, n, 1);
65     while (m--) {
66         int i, j, k;
67         scanf("%d%d%d", &i, &j, &k);
68         int lb = 0, ub = n;
69         while (ub - lb > 1) {
70             int mid = (lb + ub) >> 1;
71             int c = query(i, j, num[mid], 1, n, 1);
72             if (c >= k) ub = mid;
73             else lb = mid;
74         }
75         printf("%d
", num[ub]);
76     }
77     return 0;
78 }