在发这个帖子之前已经跟着题解区和讨论区的引导自行 debug 过代码了，然而仍然在测试点 $1$ 因 line 1 column 1, read 5, expected 9 而 WA 90 分

思路是在权值线段树合并的同时计算交换前后对答案的贡献取最小值，求助各位大佬

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=500000+5;
int n,w1,w2;
namespace segtree{
	struct seg{
		int l,r;
		ll sum;
	};
	seg tree[maxn*80];
	int used;
	inline void pushup(int root){
		tree[root].sum=tree[tree[root].l].sum+tree[tree[root].r].sum;
	}
	int edit(int qx,int l,int r){
		int root=++used;
		tree[root].sum++;
		if(l==r)return root;
		int mid=(l+r)>>1;
		if(qx<=mid)tree[root].l=edit(qx,l,mid);
		else tree[root].r=edit(qx,mid+1,r);
		return root;
	}
	int merge(int a,int b,int l,int r){
		if(!a||!b)return a+b;
		if(l==r){
			tree[a].sum+=tree[b].sum;return a;
		}
		w1+=1ll*tree[tree[a].r].sum*tree[tree[b].l].sum;
		w2+=1ll*tree[tree[b].r].sum*tree[tree[a].l].sum;
		int mid=(l+r)>>1;
		tree[a].l=merge(tree[a].l,tree[b].l,l,mid);
		tree[a].r=merge(tree[a].r,tree[b].r,mid+1,r);
		pushup(a);
		return a;
	}
}
ll ans;
void dfs(int &root){
	int v;scanf("%d",&v);
	if(!v){
		int l=0,r=0;
		dfs(l),dfs(r),root=segtree::merge(l,r,1,n);
		ans+=min(w1,w2);
		w1=w2=0;
	}
	else root=segtree::edit(v,1,n);
}
int main(){
	scanf("%d",&n);
	int root=0;dfs(root);
	printf("%lld\n",ans);
}