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+线段树合并）

最新文章

热门文章