题解 [SCOI2008]斜堆

好题。一道很有趣的性质提。

因为自己搞错结论然后改了 1h（悲

闲话少说，切入正题——

这是不断插入的，所以根据套路我们会考虑最后一个插入的节点的性质。显然满足：

它是从根不停往左走的路上。
它没有右子树。

但是这样的点有很多，我们来深入分析。性质 1 说明这些点在一条链上，我们知道插入的时候会将当前节点的左右儿子变换。我们要由此引出第三条性质：一个节点不可能只有右儿子。这是显而易见的。根据性质三，我们可以知道，假设我们有 \(a, b\) 满足性质 1 与性质 2，\(a\) 深度比 \(b\) 大，则会交换 \(b\) 的左右儿子，\(b\) 只有右儿子，与第三条性质相悖。

那么我们就可以知道了，最后一个插入的节点必然是深度最小的满足性质 1，2 的节点。

但是也有例外，假设我们这样一棵条链：0-1为什么画图都要偷懒！正确答案应该是 1 0，但是如果按照上面的算法就是 0 1。

我们会发现删除 1 反转它的祖先依旧可以保证所有节点满足性质 3。这是因为首先它的父亲是 0 本身满足性质 1 与性质 2 没有右子树，其次 1 是叶子节点，没有子树，因此不需要给 0 新增儿子。

我们能得到另外一个性质，令当前满足性质 1 性质 2 的最浅节点为 \(d\)，若 \(d\) 的左儿子是叶子节点，就选择删除 \(d\) 的左儿子，否则删除 \(d\)。

删除以后把自己的子树给父亲，反转祖宗的左右儿子。

//SIXIANG

#include <iostream>

#include <vector>

#define MAXN 100000

#define QWQ cout << "QWQ" << endl;

using namespace std;

int ch[MAXN + 10][3], a[MAXN + 10], rt;

//0 左儿子 1 右儿子 2 父亲

int Find() {

	int now = rt;

	while(1) {

		if(ch[now][1] == -1) return now;

		now = ch[now][0];

	}

}

bool isleaf(int x) {

	return ((ch[x][0] == ch[x][1]) && (ch[x][0] == -1));

}

int Delete() {

	int d = Find();

	if(d != -1 && isleaf(ch[d][0])) d = ch[d][0];

	if(d == rt)

		rt = ch[d][0];

	else {

		ch[ch[d][2]][0] = ch[d][0];

		if(ch[d][0] != -1) ch[ch[d][0]][2] = ch[d][2];

		int to = ch[d][2];

		while(to != -1) {

			swap(ch[to][0], ch[to][1]);

			to = ch[to][2];

		}

	}

	return d;

}

int main() {

	int n; cin >> n;

	for(int p = 0; p <= n; p++) ch[p][0] = ch[p][1] = ch[p][2] = -1;

	for(int p = 1; p <= n; p++) {

		cin >> a[p];

		if(a[p] >= 100) ch[a[p] - 100][1] = p, ch[p][2] = a[p] - 100;

		else ch[a[p]][0] = p, ch[p][2] = a[p];

	}

	for(int p = 0; p <= n; p++)

		a[n - p] = Delete();

	for(int p = 0; p <= n; p++)

		cout << a[p] << ' ';

}

巴特西

题解 [SCOI2008]斜堆

最新文章

热门文章