BZOJ4919 大根堆（树形dp+线段树合并）

本文主要是介绍BZOJ4919 大根堆（树形dp+线段树合并），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

用 multiset 启发式合并贪心维护 LIS 的做法就不多说了，网上题解一大堆，着重讲一下线段树合并维护 \(dp\)。

\(O(n^2)\) 的 \(dp\) 非常显然。离散化后，设 \(dp[u][i]\) 表示节点 \(u\) 的子树中，最大值为 \(i\) 时最多取多少个节点。转移时考虑是否将节点 \(u\) 加入大根堆并分类讨论。

这样的状态不支持快速合并。考虑优化状态，设 \(dp[u][i]\) 表示节点 \(u\) 的子树中，最大值 \(\le i\) 时最多取多少个节点，并尝试使用线段树合并来维护。

转移同样考虑两种情况。如果 \(u\) 不取，那么直接 \(dp[u][i] = \sum dp[v][i]\) 即可，将 \(u\) 的儿子的线段树合并。合并之后，如果 \(u\) 取，就要求子树中取的最大值都 \(\lt val[u]\)，那么要用 \(\max\limits_{i \lt val[u]}dp[u][i]+1\) 去更新 \(dp[u][\ge val[u]]\)。

注意到，根据状态的设计，\(dp[u]\) 其实是一个单调不减的序列，所以 \(\max\limits_{i \lt val[u]} dp[u][i]+1\) 其实相当于 \(dp[u][val[u]-1]+1\)。同时由于 \(dp[u]\) 单调不减，所以 \(dp[u][\ge val[u]]\) 中会被更新的值是一段左端点为 \(val[u]\) 的区间，这段区间的值都是 \(dp[u][val[u]-1]\)。

于是，可以二分出区间的右端点。具体地，二分找到最后一个 \(i\) 使得 \(dp[u][i] \lt dp[u][val[u]-1]+1\)，然后在线段树上将区间 \([val[u],i]\) 覆盖或直接 \(+1\) 即可，需要标记永久化。

综上所述，该算法的时间复杂度为 \(O(n \log^2 n)\)。

/**
 * @file:           BZOJ4919.cpp
 * @author:         yaoxi-std
 * @url:            
*/
#pragma GCC optimize ("O2")
#pragma GCC optimize ("Ofast", "inline", "-ffast-math")
#pragma GCC target ("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
using namespace std;
#define resetIO(x) \
    freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define debug(fmt, ...) \
    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)
template <class _Tp>
inline _Tp& read(_Tp& x) {
    bool sign = false; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
    return sign ? (x = -x) : x;
}
template <class _Tp>
inline void write(_Tp x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar((x % 10) ^ 48);
}
bool m_be;
using ll = long long;
const int MAXN = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n, m, a[MAXN], fa[MAXN], val[MAXN];
vector<int> g[MAXN];
struct SegmentTree {
    struct Node {
        int ls, rs, sum;
    } nd[MAXN * 25];
    int tot, rt[MAXN];
    int& operator[](int i) { return rt[i]; }
    void update(int& i, int l, int r, int ql, int qr, int v) {
        if (ql > qr) return;
        if (!i) i = ++tot;
        if (ql <= l && r <= qr) return void(nd[i].sum += v);
        int mid = (l + r) >> 1;
        if (ql <= mid) update(nd[i].ls, l, mid, ql, qr, v);
        if (qr > mid) update(nd[i].rs, mid + 1, r, ql, qr, v);
    }
    int query(int i, int l, int r, int p) {
        if (!i || !p) return 0;
        if (l == r) return nd[i].sum;
        int mid = (l + r) >> 1;
        if (p <= mid) return nd[i].sum + query(nd[i].ls, l, mid, p);
        return nd[i].sum + query(nd[i].rs, mid + 1, r, p);
    }
    void merge(int& x, int y, int l, int r) {
        if (!x || !y) return void(x = x | y);
        if (l == r) return void(nd[x].sum += nd[y].sum);
        int mid = (l + r) >> 1;
        merge(nd[x].ls, nd[y].ls, l, mid);
        merge(nd[x].rs, nd[y].rs, mid + 1, r);
        nd[x].sum += nd[y].sum;
    }
} sgt;
void dfs(int u) {
    for (auto v : g[u]) dfs(v), sgt.merge(sgt[u], sgt[v], 1, m);
    int tmp = sgt.query(sgt[u], 1, m, a[u] - 1) + 1;
    int l = a[u], r = m, pos = a[u] - 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (sgt.query(sgt[u], 1, m, mid) < tmp)
            l = mid + 1, pos = mid;
        else
            r = mid - 1;
    }
    sgt.update(sgt[u], 1, m, a[u], pos, 1);
}
bool m_ed;
signed main() {
    read(n);
    for (int i = 1; i <= n; ++i)
        read(a[i]), read(fa[i]), val[i] = a[i], g[fa[i]].push_back(i);
    sort(val + 1, val + n + 1), m = unique(val + 1, val + n + 1) - val - 1;
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(val + 1, val + m + 1, a[i]) - val;
    dfs(1), write(sgt.query(1, 1, m, m)), putchar('\n');
    return 0;
}

这篇关于BZOJ4919 大根堆（树形dp+线段树合并）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！