题解：P2171 Hz 吐泡泡

· · 题解

本文中的二叉搜索树指 BST，它的其他译名包括二叉查找树、二叉排序树等。

本题加强了数据，把所有暴力建二叉搜索树的题解全卡掉了，我来写一个复杂度正确的笛卡尔树题解。

笛卡尔树是一棵特殊的二叉树，它的每个节点有两个权值 (x_i,y_i)，满足：

由题意，我们需要建的树满足以下性质：

先对所有泡泡排序，然后跑 P5854 【模板】笛卡尔树 的线性建树方式即可。需要注意的是，本题中的堆权和搜索树权与该题是反过来的。

时间复杂度 O(n\log n)。

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(y < x) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

template<int mod>
inline unsigned int down(unsigned int x) {
    return x >= mod ? x - mod : x;
}

template<int mod>
struct Modint {
    unsigned int x;
    Modint() = default;
    Modint(unsigned int x) : x(x) {}
    friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
    friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
    friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
    friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
    friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
    friend Modint operator/(Modint a, Modint b) {return a * ~b;}
    friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
    friend Modint operator~(Modint a) {return a ^ (mod - 2);}
    friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
    friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
    friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
    friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
    friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
    friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
    friend Modint& operator++(Modint& a) {return a += 1;}
    friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
    friend Modint& operator--(Modint& a) {return a -= 1;}
    friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
    friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
    friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};

const int N = 3e5 + 5;

int n, a[N], idx[N], L[N], R[N], stk[N], top, dis[N];

void dfs1(int u) {
    if(L[u]) {
        dis[L[u]] = dis[u] + 1;
        dfs1(L[u]);
    }
    if(R[u]) {
        dis[R[u]] = dis[u] + 1;
        dfs1(R[u]);
    }
}

void dfs2(int u) {
    if(L[u]) dfs2(L[u]);
    if(R[u]) dfs2(R[u]);
    cout << a[u] << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, n) idx[i] = i;
    sort(idx + 1, idx + 1 + n, [&](int x, int y) {
        return a[x] < a[y];
    });
    stk[++top] = idx[1];
    rep(i, 2, n) {
        while(top && stk[top] > idx[i]) --top;
        if(top) {
            L[idx[i]] = R[stk[top]];
            R[stk[top]] = idx[i];
        }
        else L[idx[i]] = stk[1];
        stk[++top] = idx[i];
    }
    dis[1] = 1;
    dfs1(1);
    cout << "deep=" << *max_element(dis + 1, dis + 1 + n) << endl;
    dfs2(1);
    return 0;
}