P1377 [TJOI2011] 树的序题解

wxzzzz · 2024-01-13 13:01:54 · 题解

思路

按照题意建立二叉查找树，直接按先序遍历。

这是朴素的建树方式插入一个数 x 的操作：

如果树为空，直接新建一个节点，权值为 x。
如果树不为空，从根节点开始遍历，令当前遍历到的节点为 p，若 x 的权值比 p 小，则令 p 转移到 p 的左儿子，否则转移到 p 的右儿子。
重复操作 2 直到 p 表示一个空节点，将这个节点的权值赋为 x。

void insert(int x) {
    if (!idt) {
        t[++idt] = {0, 0, x};
        return;
    }

    int p = 1;

    while (p) {
        if (x < t[p].val) {
            if (!t[p].ls)
                break;

            p = t[p].ls;
        } else {
            if (!t[p].rs)
                break;

            p = t[p].rs;
        }
    }

    if (x < t[p].val) {
        t[p].ls = ++idt;
        t[idt].val = x;
    } else {
        t[p].rs = ++idt;
        t[idt].val = x;
    }
}

上面代码的平均复杂度为 O(\log n)，但当 a_i 有单调性时，二叉查找树会退化成一条链，insert 的复杂度退化成 O(n)。

考虑优化 insert。

可以发现根本没必要从根节点开始遍历，因为 x 最终只可能插到这两个位置：

权值比 x 大的权值最小的节点的左儿子。
权值比 x 小的权值最大的节点的右儿子。

这两个东西都可以用 set 维护。

把 x 放到任意一个有空的位置即可。

注意，朴素遍历方式会优先放位置 1，因此在这题要优先放位置 1。

代码

#include <bits/stdc++.h>
using namespace std;
int n, idt, a[100005];
set<pair<int, int>> p;
set<pair<int, int>>::iterator it;
struct node {
    int ls, rs, val;
} t[100005];
void insert(int x) {
    if (!idt) {
        t[++idt] = {0, 0, x};
        p.insert({x, 1});
        return;
    }

    it = p.lower_bound({x, 0});

    if (it == p.end() || t[(*it).second].ls)
        it--, t[(*it).second].rs = ++idt, t[idt].val = x;
    else
        t[(*it).second].ls = ++idt, t[idt].val = x;

    p.insert({x, idt});
}
void dfs(int p) {
    cout << t[p].val << ' ';

    if (t[p].ls)
        dfs(t[p].ls);

    if (t[p].rs)
        dfs(t[p].rs);
}
int main() {
    cin >> n;

    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        insert(x);
    }

    dfs(1);
    return 0;
}

P1377 [TJOI2011] 树的序 题解

思路

代码

P1377 [TJOI2011] 树的序题解