[SCOI2008]斜堆

admin LV 10 SU @ 2026-5-10 0:59:56

本题相当于 P14280 的弱化版。本文同本人在 P14280 的题解。

让我们从局部入手，研究最终树上的一个以 $u$ 为根的子树，假设它有左子树 $A$ 和右子树 $B$ （均不为空，边界情况后面再考虑），大小分别为 $s_A$ 和 $s_B$ ，下面用 $a$ 和 $b$ 分别表示它们中的某个节点。那么我们在 $u$ 上只用管把 $A$ 和 $B$ 中的节点正确在 $u$ 点分流就好了。下面就是在研究可以得到 $u$ 子树形态的插入序列。

我们在这个子树上的插入序列按 $u$ 之前和 $u$ 之后的划分成两部分。那么在 $u$ 之前的第一部分必然属于一个子树，第一部分插入完后插入 $u$ 时后暂时成为 $u$ 的左子树（可以发现这里不会改变左子树的内部结构，这是我们可以在上面只考虑 $u$ 点的分流的基础）；在 $u$ 后的，当到达 $u$ 这个点时，先进行交换左右子树的操作，然后插入进 $u$ 此时的左子树，因此在 $u$ 后插入的点，其归属（相对于 $u$ 的两个子树而言）必定是交替的，换句话说就是以 $abab\cdots$ 或 $baba\cdots$ 的形式出现。

同时对于 $u$ 后面插入的点，其第一个必定不归属于 $u$ 之前插入的点所归属的，其第二个必定归属于 $u$ 之前插入的点所归属的。

那么如果在 $u$ 前插入的都是 $A$ 子树的节点，综合上述信息，可以得到插入序列必定形如

aaa\cdots a~u~baba\cdots ba

如果在 $u$ 前插入的都是 $B$ 子树的节点，综合上述信息，可以得到插入序列必定形如

bbb\cdots b~u~a~baba\cdots ba

当我们确定了 $u$ 属于哪种范式时，我们就可以先递归 $u$ 的左右儿子，然后依次把 $B$ 的序列填入 $u$ 范式中所有 $b$ 的位置， $A$ 同理，就唯一确定了 $u$ 的序列。

那么我们唯一可以操作来寻找最小最大的空间就再与确定 $u$ 的范式这一步。

考虑范式可以使用的条件

对于第一个范式 $\underbrace{aaa\cdots a}_{\text{一共 }c\text{ 个 }a}~u~\underbrace{baba\cdots ba}_{\text{一共 }k\text{ 个 }ba}$，则有 $c\ge0,k\ge0,s_A=c+k,s_B=k$ ，得到 $s_A\ge s_B$ 就可以用。
对于第二个范式 $\underbrace{bbb\cdots b}_{\text{一共 }c\text{ 个 }b}~u~a~\underbrace{baba\cdots ba}_{\text{一共 }k\text{ 个 }ba}$，则有 $c\ge0,k\ge0,s_A=k+1,s_B=c+k$ ，可以得到 $s_A\le s_B+1$ 。

因此只有当 $s_A=s_B$ 或 $s_A=s_B+1$ 时我们才有两个范式可用，其它时候只能使用其中的一种范式。

当 $s_A=s_B$ 时，我们可以有 $u~baba\cdots ba$ 和 $b~u~a~baba\cdots ba$ 两种范式可用，因为小根堆的性质保证了 $u<a$ 且 $u<b$ ，所以当求最小排列时用第一种范式最优，求最大排列时用第二种范式最优。
当 $s_A=s_B+1$ 时，我们可以有 $u~a~baba\cdots ba$ 和 $a~u~baba\cdots ba$ 两种范式可用，同上，当求最小排列时用第一种范式最优，求最大排列时用第二种范式最优。

至此我们得到了大部分的做法，接下来考虑一些边界情况：

即没有左儿子也没有右儿子，那么序列就为其自身。
有左儿子没有右儿子。当左儿子大小恰为 $1$ 时和 $s_A=s_B+1$ 差不多，否则就只能把 $u$ 加到左儿子序列右侧。
没有左儿子有右儿子。显然这种情况不合法，提前判掉就可以了。

那么依照上面的思路我们就可以写出来一份 $\mathcal O(n^2)$ 的代码：

:::success[ $\mathcal O(n^2)$ 的代码]

#include <cassert>
#include <iostream>
#define endl '\n'

using namespace std;

constexpr int N = 2e5;
constexpr int XN = N + 10;
// g 是临时数组，f 和 g 都使用 dfn + i - 1 的方式来存储对应子树的答案
int n, ls[XN], rs[XN], dfn[XN], siz[XN], idx, f[XN], g[XN];

void dfs1(int u) {
    siz[u] = 1, dfn[u] = ++idx;
    ls[u] && (dfs1(ls[u]), siz[u] += siz[ls[u]]);
    rs[u] && (dfs1(rs[u]), siz[u] += siz[rs[u]]);
}

#define PR (g[dfn[u] + (c++)] = u)
#define PA (g[dfn[u] + (c++)] = f[dfn[ls[u]] + (cl++)])
#define PB (g[dfn[u] + (c++)] = f[dfn[rs[u]] + (cr++)])
#define SA (siz[ls[u]])
#define SB (siz[rs[u]])
#define F(__X__) for (int __i__ = 0; __i__ < (__X__); __i__++)

enum {
    MIN, MAX
};

void dfs2(int u, int tag) {
    ls[u] && (dfs2(ls[u], tag), 0);
    rs[u] && (dfs2(rs[u], tag), 0);
    int c = 0, cl = 0, cr = 0;
    if (SA < SB) { // 采用 BB...B U A BABA...BA 范式
        F(SB - SA + 1) PB;
        PR;
        F(SA - 1) PA, PB;
        PA;
    } else if (SA > SB + 1) { // 采用 AA...A U BABA...BA 范式
        F(SA - SB) PA;
        PR;
        F(SB) PB, PA;
    } else if (SA == SB) { // 依情况
        if (tag == MIN) { // 采用 U BABA...BA 范式
            PR;
            F (SA) PB, PA;
        } else if (SA) { // 采用 B U A BABA...BA 范式
            PB, PR;
            F(SA - 1) PA, PB;
            PA;
        } else PR; // 合并无子特判
    } else if (SA == SB + 1) { // 依情况
        if (tag == MIN) { // 采用 U A BABA...BA 范式
            PR;
            F (SB) PA, PB;
            PA;
        } else { // 采用 A U BABA...BA 范式
            PA, PR;
            F(SB) PB, PA;
        }
    } else assert(false);
    assert(c == siz[u]);
    assert(cl == siz[ls[u]]);
    assert(cr == siz[rs[u]]);
    for (int i = 0; i < siz[u]; i++)
        f[dfn[u] + i] = g[dfn[u] + i];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n, n++;
    for (int i = 2; i <= n; i++) {
        int fat; cin >> fat;
        if (fat < 100) ls[fat + 1] = i;
        else rs[fat - 100 + 1] = i;
    }
    for (int i = 1; i <= n; i++)
        if ((ls[i] && ls[i] < i) || (rs[i] && rs[i] < i) || (!ls[i] && rs[i]))
            return cout << "impossible" << endl, 0;
    dfs1(1);
    dfs2(1, MIN);
    for (int i = 1; i <= n; i++)
        cout << f[i] - 1 << " \n"[i == n];
    return 0;
}

:::

上面的代码已经足以通过本题。下面是其加强版的优化。

这道题数据范围是 $10^5$ ，考虑优化。可以使用 dsu on tree 的思路，让一个点 $u$ 的合并复杂度只和其较轻的一个子树的的大小相关。具体来说可以发现我们上面的哪些范式都可以从后往前往某个子树的序列中插入另一个子树的序列及当前节点 $u$ 做到，因此可以用链表来维护，具体实现看代码。这样我们就把代码优化到了 $\mathcal O(n\log n)$ ，可以通过本题的加强版。

:::success[ $\mathcal O(n\log n)$ 的代码]

#include <cassert>
#include <iostream>
#define endl '\n'

using namespace std;

constexpr int N = 2e5;
constexpr int XN = N + 10;
int n, ls[XN], rs[XN], dfn[XN], siz[XN], idx, f[XN];
int pe[XN], ne[XN];

void dfs1(int u) {
    siz[u] = 1, dfn[u] = ++idx;
    ls[u] && (dfs1(ls[u]), siz[u] += siz[ls[u]]);
    rs[u] && (dfs1(rs[u]), siz[u] += siz[rs[u]]);
}

enum {
    MIN, MAX
};

// 用链表来支持常数时间插入点
struct List {
    int s, t;
};

// 在 p 后面插入一个节点 q
void insne(int p, int q) {
    pe[q] = p, ne[q] = ne[p];
    if (ne[p]) pe[ne[p]] = q;
    ne[p] = q;
}

// 在 p 前面插入一个节点 q
void inspe(int p, int q) {
    pe[q] = pe[p], ne[q] = p;
    if (pe[p]) ne[pe[p]] = q;
    pe[p] = q;
}

#define SA (siz[ls[u]])
#define SB (siz[rs[u]])

void print(const List& l) {
    for (int i = l.s; i != ne[l.t]; i = ne[i])
        cout << i  - 1 << ' ';
    cout << endl;
}

List dfs2(int u, int tag) {
    pe[u] = ne[u] = 0;
    if (!ls[u]) return List{u, u};
    // 这里和暴力代码实现不同，这里提前拿出来判掉
    if (!rs[u]) {
        List l = dfs2(ls[u], tag);
        if (siz[ls[u]] == 1) {
            if (tag == MIN) {
                insne(u, l.s);
                return List{ u, l.s };
            } else {
                inspe(u, l.s);
                return List{ l.s, u };
            }
        } else {
            insne(l.t, u);
            return List{ l.s, u };
        }
    }
    List la = dfs2(ls[u], tag);
    List lb = dfs2(rs[u], tag);
    if (SA < SB) {
        int p = lb.t, q = la.t;
        for (int i = 0; i < SA; i++) {
            int t = pe[q];
            insne(p, q);
            q = t, p = pe[p];
        }
        inspe(la.s, u);
        return List{ lb.s, la.t };
    } else if (SA > SB + 1) {
        int p = la.t, q = lb.t;
        for (int i = 0; i < SB; i++) {
            int tp = pe[p], tq = pe[q];
            inspe(p, q);
            p = tp, q = tq;
        }
        insne(p, u);
        return List{ la.s, la.t };
    } else if (SA == SB) {
        if (tag == MIN) {
            int p = lb.t, q = la.t;
            for (int i = 0; i < SA; i++) {
                int t = pe[q];
                insne(p, q);
                q = t, p = pe[p];
            }
            inspe(lb.s, u);
            return List{ u, la.t };
        } else {
            int p = lb.t, q = la.t;
            for (int i = 0; i < SA; i++) {
                int t = pe[q];
                insne(p, q);
                q = t, p = pe[p];
            }
            insne(lb.s, u);
            return List{ lb.s, la.t };
        }
    } else if (SA == SB + 1) {
        if (tag == MIN) {
            int p = la.t, q = lb.t;
            for (int i = 0; i < SB; i++) {
                int tp = pe[p], tq = pe[q];
                inspe(p, q);
                p = tp, q = tq;
            }
            inspe(p, u);
            return List{ u, la.t };
        } else {
            int p = la.t, q = lb.t;
            for (int i = 0; i < SB; i++) {
                int tp = pe[p], tq = pe[q];
                inspe(p, q);
                p = tp, q = tq;
            }
            insne(p, u);
            return List{ la.s, la.t };
        }
    }
    assert(false);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n, n++;
    for (int i = 2; i <= n; i++) {
        int fat; cin >> fat;
        if (fat < 100) ls[fat + 1] = i;
        else rs[fat - 100 + 1] = i;
    }
    for (int i = 1; i <= n; i++)
        if ((ls[i] && ls[i] < i) || (rs[i] && rs[i] < i) || (!ls[i] && rs[i]))
            return cout << "impossible" << endl, 0;
    dfs1(1);
    print(dfs2(1, MIN));
    return 0;
}

:::

ID

2731

时间

800ms

内存

125MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

信息

状态

开发

支持

关于

1 条题解

[SCOI2008]斜堆

信息

状态

开发

支持

关于

还没有账户？

登录