BZOJ1078【SCOI2008】斜堆 <可并堆>

Problem

【SCOI2008】斜堆

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;162\;MB}$

Description

斜堆$\mathrm{(skew\;heap)}$是一种常用的数据结构。它也是二叉树，且满足与二叉堆相同的堆性质：每个非根结点的值都比它父亲大。因此在整棵斜堆中，根的值最小。但斜堆不必是平衡的，每个结点的左右儿子的大小关系也没有任何规定。在本题中，斜堆中各个元素的值均不相同。
在斜堆$H$中插入新元素$X$的过程是递归进行的：

• 当$H$为空或者$X$小于$H$的根结点时X变为新的树根，而原来的树根（如果有的话）变为$X$的左儿子。
• 当$X$大于$H$的根结点时，$H$根结点的两棵子树交换，而$X$（递归）插入到交换后的左子树中。

给出一棵斜堆，包含值为$0\sim n$的结点各一次。求一个结点序列，使得该斜堆可以通过在空树中依次插入这些结点得到。
如果答案不惟一，输出字典序最小的解。输入保证有解。

Input

第一行包含一个整数$n$。
第二行包含$n$个整数$d_1,d_2,\cdots,d_n$，$d_i<100$表示$i$是$d_i$的左儿子，$d_i\ge100$表示$i$是$d_i-100$的右儿子。
显然$0$总是根，所以输入中不含$d_0$。

Output

仅一行，包含$n+1$整数，即字典序最小的插入序列。

Sample Input

6
100 0 101 102 1 2

Sample Output

0 1 2 3 4 5

标签：可并堆 斜堆

Solution

探究斜堆性质的好题，可以围观$\mathrm{Mato}$的题解。

考虑每次找到最后插入的结点，删除并维护到插入前的状态。那么我们需要探究一些斜堆的性质。

1. 最后插入的结点一定是一个极左结点，即从根到它的路径都是向左走，因为最后插入后没有再交换过子树。
2. 最后插入的结点一定没有右子树。易发现所有右子树都是因为插入结点而从左结点交换而来，而最后插入的结点的子树中一定不会插入新的结点，故一定不会有右子树。
3. 最后插入结点时，其到根的结点一定会交换左右子树，因此这个结点到根的路径上的所有结点一定都有左右子树。

综上，最后插入的结点一定是从根结点一直向左走遇到的第一个无右子树的结点。特别地，如果此结点的左子结点是叶子，那么两者均可选，这时应该先选叶子结点以使字典序最小。模拟$n+1$次即可

Code

#include <bits/stdc++.h>
#define MAX_N 50
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, rt, l[MAX_N+5], r[MAX_N+5];
int f[MAX_N+5];    stack <int> sta;
void find() {
    int u = rt;	while (~r[u]) u = l[u];
    if (~l[u] && l[l[u]] == r[l[u]]) u = l[u];
    sta.push(u);	if (u == rt) rt = l[rt];
    if (~f[u]) l[f[u]] = l[u], f[l[u]] = f[u];
    for (int v = f[u]; ~v; v = f[v]) swap(l[v], r[v]);
}
int main() {
    read(n), f[0] = -1;
    memset(l, -1, sizeof l), memset(r, -1, sizeof r);
    for (int i = 1, d; i <= n; i++)
        read(d), (d < 100 ? l[d] = i : r[d-100] = i), f[i] = d < 100 ? d : d-100;
    for (int i = 0; i <= n; i++) find();
    while (!sta.empty()) printf("%d ", sta.top()), sta.pop();
    return 0;
}