bzoj1078: [SCOI2008]斜堆

非常详细，我就不写了

传送门：http://www.cppblog.com/MatoNo1/archive/2012/10/07/192131.html

const int N = 60;
struct Node {
	int V, Lc, Rc, Size, C[N];
} Tr[N];
int n;
int L[N], R[N], C[N];

inline void Input() {
	scanf("%d", &n);
	For(i, 1, n) {
		int t;
		scanf("%d", &t);
		t < 100 ? Tr[t + 1].Lc = i + 1 : Tr[t - 100 + 1].Rc = i + 1;
	}
}

#define MC memcpy
inline void dfs(int x) {
	if(!x) return;
	dfs(Tr[x].Lc), dfs(Tr[x].Rc);
	Tr[x].Size = Tr[Tr[x].Lc].Size + Tr[Tr[x].Rc].Size + 1;
	clr(Tr[x].C, 0), clr(C, 0);
	int a = Tr[Tr[x].Lc].Size , b = Tr[Tr[x].Rc].Size;
	MC(L, Tr[Tr[x].Lc].C, sizeof(int) * a), MC(R, Tr[Tr[x].Rc].C, sizeof(int) * b);
	int p = 0;
	if(a < b){
		memcpy(C, R, sizeof(int) * (b - a + 1));
		p = b - a + 1;
		C[p++] += x;
		int p1 = 0, p2 = b - a + 1;
		Rep(i, a - 1) C[p++] = L[p1++], C[p++] = R[p2++];
		C[p++] = L[p1++];
	}else if(a == b){
		C[p++] = x;
		Rep(i, a) C[p++] = R[i], C[p++] = L[i];
	}else if(a == b + 1) {
		C[p++] = x, C[p++] = L[0];
		Rep(i, b) C[p++] = R[i], C[p++] = L[i + 1];
	}else {
		Rep(i, a - b) C[p++] = L[i];
		C[p++] = x;
		Rep(i, b) C[p++] = R[i], C[p++] = L[i + a - b];
	}
	MC(Tr[x].C, C, sizeof(int) * Tr[x].Size);
}

inline void Solve() {
	dfs(1);
	Rep(i, Tr[1].Size) printf("%d ", Tr[1].C[i] - 1);
	printf("\n");
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1078");
	#endif
	Input();
	Solve();
	return 0;
}