RE 12分 求条

#include<bits/stdc++.h>
using namespace std;
int const N=200005;
struct p{
	long long l, r, cnt;
}tree[N*25];
long long last=0, root[N*25], sum=0, cnt[N*25], n, o, cnt1, cnt2, ans=0;
pair<long long, long long> a[N*25];
void build(long long pos, long long l, long long r, long long &x){
	x=++sum;
	if(l==r){
		tree[x].cnt=1;
		return ;
	}
	long long mid=(l+r)>>1;
	if(pos<=mid) build(pos, l, mid, tree[x].l);
	else build(pos, mid+1, r, tree[x].r);
	tree[x].cnt=tree[tree[x].l].cnt+tree[tree[x].r].cnt;
}
long long update(long long u, long long v, long long l, long long r, long long &cnt1, long long &cnt2){
	if(!u) return v;
	if(!v) return u;
	if(l==r){
		tree[u].cnt+=tree[v].cnt;
		return u;
	}
	long long mid=(l+r)>>1;
	cnt1+=tree[tree[v].l].cnt*tree[tree[u].r].cnt;
	cnt2+=tree[tree[v].r].cnt*tree[tree[u].l].cnt;
	tree[u].l=update(tree[u].l, tree[v].l, l, mid, cnt1, cnt2);
	tree[u].r=update(tree[u].r, tree[v].r, mid+1, r, cnt1, cnt2);
	tree[u].cnt=tree[tree[u].l].cnt+tree[tree[u].r].cnt;
	return u;
}
void f(long long x){
	cin>>o;
	if(o){
		cnt[x]=o;
		return ;
	}else{
		a[x]={x<<1, x<<1|1};
		f(x<<1);
		f(x<<1|1);
	}
}
void dfs(long long x){
	if(cnt[x]){
		build(cnt[x], 1, n, root[x]);
		return ;
	}
	dfs(a[x].first);
	dfs(a[x].second);
	cnt1=cnt2=0;
	long long l=root[a[x].first], r=root[a[x].second];
	root[x]=update(l, r, 1, n, cnt1, cnt2);
	ans+=min(cnt1, cnt2);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	f(1);
	dfs(1);
	cout<<ans;
	return 0;
}