代码

#include <iostream>
#include <vector>

typedef long long LL;
LL N;
LL Ans, Num1, Num2;
struct SegmentTreeNode {
	LL LChild, RChild, Num;
};
std::vector<SegmentTreeNode> SegmentTree;

LL Update(LL Value, LL L = 1, LL R = N) {
	SegmentTree.emplace_back();
	SegmentTree.back().Num++;
	if (L == R) return LL(SegmentTree.size()) - 1;
	LL Mid = (L + R) / 2;
	if (Value <= Mid) SegmentTree.back().LChild = Update(Value, L, Mid);
	else SegmentTree.back().RChild = Update(Value, Mid + 1, R);
	return LL(SegmentTree.size()) - 1;
}

LL Merge(LL Root1, LL Root2, LL L = 1, LL R = N) {
	if (Root1 == 0) return Root2;
	if (Root2 == 0) return Root1;
	if (L == R) {
		SegmentTree[Root1].Num += SegmentTree[Root2].Num;
		return Root1;
	}
	Num1 += SegmentTree[SegmentTree[Root1].RChild].Num * SegmentTree[SegmentTree[Root2].LChild].Num;
	Num2 += SegmentTree[SegmentTree[Root1].LChild].Num * SegmentTree[SegmentTree[Root2].RChild].Num;
	LL Mid = (L + R) / 2;
	SegmentTree[Root1].LChild = Merge(SegmentTree[Root1].LChild, SegmentTree[Root2].LChild, L, Mid);
	SegmentTree[Root1].RChild = Merge(SegmentTree[Root1].RChild, SegmentTree[Root2].RChild, Mid + 1, R);
	SegmentTree[Root1].Num = SegmentTree[SegmentTree[Root1].LChild].Num + SegmentTree[SegmentTree[Root1].RChild].Num;
	return Root1;
}

LL Input_Main() {
	LL Position, Value;
	std::cin >> Value;
	if (Value == 0) {
		LL LChild = Input_Main();
		LL RChild = Input_Main();
		Num1 = Num2 = 0;
		Position = Merge(LChild, RChild);
		Ans += std::min(Num1, Num2);
	} else Position = Update(Value);
	return Position;
}

int main() {
	std::cin >> N;
	SegmentTree.emplace_back();
	Input_Main();
	std::cout << Ans << '\n';
	return 0;
}

WA+RE 10pts