题解

其实很简单。。
很明显，一个节点的两个儿子，s1，s2，他们内部的逆序对是不会再改变了
然后唯一可能变的就是夸过两个儿子的答案
这个东西在线段树合并的时候顺便统计一下就可以了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=200005*20;
typedef long long LL;
LL son[N][2];
LL n;
LL rt;
LL num;//编号 
LL a[N];
LL root[N];
void Read (LL &now)
{now=++num;scanf("%lld",&a[now]);if (a[now]!=0) return ;Read(son[now][0]);Read(son[now][1]);
}
LL c[N],s1[N],s2[N];
void change (LL &now,LL l,LL r,LL x)
{if (now==0) now=++num;c[now]++;if (l==r) return ;LL mid=(l+r)>>1;if (x<=mid) change(s1[now],l,mid,x);else change(s2[now],mid+1,r,x);
}
LL Ans[N];
LL ans1,ans2;
LL Merge (LL x,LL y)
{if (x==0) return y;if (y==0) return x;c[x]+=c[y];ans1=ans1+c[s1[x]]*c[s2[y]];ans2=ans2+c[s2[x]]*c[s1[y]];s1[x]=Merge(s1[x],s1[y]);s2[x]=Merge(s2[x],s2[y]);return x;
}
void solve (LL now)
{if (a[now]!=0)//已经到了return ;solve(son[now][0]);solve(son[now][1]);Ans[now]=0;Ans[now]=Ans[son[now][0]]+Ans[son[now][1]];ans1=0;ans2=0;root[now]=Merge(root[son[now][0]],root[son[now][1]]);Ans[now]=Ans[now]+min(ans1,ans2);
}
int main()
{scanf("%lld",&n);num=0;Read(rt);/*for (LL u=1;u<=num;u++)printf("%lld %lld\n",son[u][0],son[u][1]);for (LL u=1;u<=num;u++) printf("%lld ",a[u]);printf("\n");*/LL Num=num;num=0;for (LL u=1;u<=Num;u++)if (a[u]!=0)change(root[u],1,Num,a[u]);solve(rt);printf("%lld\n",Ans[rt]);return 0;
}