题解：P6412 [COCI2008-2009#3] BST

GGapa · 2024-05-04 15:34:33 · 题解

对 BST 的性质不够了解：

• BST 性质：新插入的节点，要么接在在前驱上，要么在后继上，哪个后出现就接在哪个的上面。可以通过这一性质快速建树，可以用 set 实现 O(n \log n)，可以用双向链表实现 O(n)。

但是这道题用 set 好像过不了，不知道是不是我写挂了，因为双向链表比较快，而且好写，推荐大家通过双向量表来构建 BST。

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a), stOwxc = (b); i <= stOwxc; i++)
#define per(i, a, b) for(int i = (a), stOwxc = (b); i >= stOwxc; i--)
using namespace std;
typedef long long LL;
using VI = vector<int>;
const int N = 3e5 + 5;

struct Node {
    int pre, nxt;
};

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<int> pos(n + 2), dep(n + 2), A(n + 2);
    vector<Node> li(n + 2);
    vector<array<int, 2>> B(n + 1);
    rep(i, 1, n) {
        cin >> A[i];
        li[i].nxt = i + 1, li[i].pre = i - 1;
    }
    per(i, n, 1) {
        int &a = A[i];
        if(li[a].nxt != n + 1) B[a][0] = li[a].nxt; 
        if(li[a].pre != 0) B[a][1] = li[a].pre;
        li[li[a].nxt].pre = li[a].pre, li[li[a].pre].nxt = li[a].nxt;
    }
    LL ans = 0;
    cout << ans << '\n';
    for(int i = 2, x; i <= n; i++) {
        dep[A[i]] = max(dep[B[A[i]][0]], dep[B[A[i]][1]]) + 1;
        ans += dep[A[i]];
        cout << ans << '\n';
    }
    return 0;
}

跑的还挺快，拿到了最优解（157944996）。