线段树合并、启发式合并

首先发现每个节点是否交换孩子不影响节点子树外叶子与节点子树内叶子对答案产生的贡献。只需要对每个非叶子节点计算交换孩子与不交换孩子的贡献，将较小的值计入答案就可以完成计算。

Solution 1：

考虑线段树合并维护节点子树内每个权值的出现次数，合并时遍历左儿子的线段树，对于在左儿子中出现过的每个叶子节点权值 $x$ 求右儿子中有多少个权值比 $x$ 更小的叶子节点以计算不交换左右儿子时当前节点子树的贡献。由于叶节点权值两两不同，交换左右儿子的贡献可以使用不交换左右儿子时的贡献计算。总体时间复杂度 $O(n^2 \log n)$，继续优化。

考虑启发式合并，对于每个节点计算时遍历其叶结点数量更少的儿子，由于节点子树中的叶子数量至少是其叶结点数量更少的孩子的叶子数量的两倍，每个权值至多被遍历 $O(\log n)$ 次。

总体时间复杂度 $O(n \log^2 n)$。

#include<bits/stdc++.h>
using namespace std;
struct Segment{int w,ls,rs;}s[200'005*20];
int n,m,seg,ro[400'005];
vector<int> *v[400'005];
long long ans;
void update(int &u,int l,int r,int p){
    if(u==0) u=++seg;
    if(l==r) return ++s[u].w,void();
    int mid=(l+r)>>1;
    if(p<=mid) update(s[u].ls,l,mid,p);
    else update(s[u].rs,mid+1,r,p);
    s[u].w=s[s[u].ls].w+s[s[u].rs].w;
}
int query(int u,int l,int r,int ql,int qr){
    if(l>=ql&&r<=qr) return s[u].w;
    int ret=0,mid=(l+r)>>1;
    if(ql<=mid) ret+=query(s[u].ls,l,mid,ql,qr);
    if(qr>mid) ret+=query(s[u].rs,mid+1,r,ql,qr);
    return ret;
}
int merge(int x,int y,int l,int r){
    if(x==0||y==0) return x+y;
    if(l==r) return s[x].w+=s[y].w,x;
    int mid=(l+r)>>1;
    s[x].ls=merge(s[x].ls,s[y].ls,l,mid);
    s[x].rs=merge(s[x].rs,s[y].rs,mid+1,r);
    s[x].w=s[s[x].ls].w+s[s[x].rs].w;
    return x;
}
void dfs(int x){
    int w=0,lson=0,rson=0;
    scanf("%d",&w);
    if(w!=0){
        update(ro[x],1,n,w);
        v[x]=new vector<int>;
        (*v[x]).push_back(w);
    }
    else{
        lson=++m,dfs(lson);
        rson=++m,dfs(rson);
        if(rson-lson>m-rson+1) swap(lson,rson);
        long long suml=0ll,sumr=0ll;
        for(int i:*v[lson]){
            if(i!=1) suml+=query(ro[rson],1,n,1,i-1);
            if(i!=n) sumr+=query(ro[rson],1,n,i+1,n);
        }
        ans+=min(suml,sumr);
        for(int i:*v[lson]) (*v[rson]).push_back(i);
        v[x]=v[rson];
        ro[x]=merge(ro[lson],ro[rson],1,n);
    }
}
int main(){
    scanf("%d",&n);
    m=1,dfs(m);
    printf("%lld\n",ans);
    return 0;
}

Solution 2：

观察题解，发现可以直接在线段树合并的过程中计算交换前后的逆序对数的事实。

从线段树本身的性质出发，对于线段树的每个非叶子节点，其左儿子代表一段值域，右儿子也代表一段值域。使用 $lson,rson$ 分别表示当前节点在题目给定的树上的左儿子和右儿子，合并 $lson,rson$ 的线段树时，对于两棵线段树上位置相同的非叶子节点 $x$，其对交换前序列的逆序对贡献为 $\bf{lson}$ 的节点 $\bf{x}$ 的右儿子所代表的值域中的权值数量乘以 $\bf{rson}$ 的节点 $\bf{x}$ 的左儿子代表的值域中的权值数量。同理，对交换后序列的逆序对贡献为 $\bf{lson}$ 的节点 $\bf{x}$ 的左儿子所代表的值域中的权值数量乘以 $\bf{rson}$ 的节点 $\bf{x}$ 的右儿子代表的值域中的权值数量。只需要实现线段树的更新与合并就可以通过本题。

时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
struct Segment{int w,ls,rs;}s[200'005*20];
int n,m,seg,ro[400'005];
long long ans,suml,sumr;
void update(int &u,int l,int r,int p){
    if(u==0) u=++seg;
    if(l==r) return ++s[u].w,void();
    int mid=(l+r)>>1;
    if(p<=mid) update(s[u].ls,l,mid,p);
    else update(s[u].rs,mid+1,r,p);
    s[u].w=s[s[u].ls].w+s[s[u].rs].w;
}
int merge(int x,int y,int l,int r){
    if(x==0||y==0) return x+y;
    if(l==r) return s[x].w+=s[y].w,x;
    int mid=(l+r)>>1;
    suml+=1ll*s[s[x].ls].w*s[s[y].rs].w;
    sumr+=1ll*s[s[x].rs].w*s[s[y].ls].w;
    s[x].ls=merge(s[x].ls,s[y].ls,l,mid);
    s[x].rs=merge(s[x].rs,s[y].rs,mid+1,r);
    s[x].w=s[s[x].ls].w+s[s[x].rs].w;
    return x;
}
void dfs(int x){
    int w=0,lson=0,rson=0;
    scanf("%d",&w);
    if(w!=0) return update(ro[x],1,n,w);
    lson=++m,dfs(lson);
    rson=++m,dfs(rson);
    suml=0ll,sumr=0ll;
    ro[x]=merge(ro[lson],ro[rson],1,n);
    ans+=min(suml,sumr);
}
int main(){
    scanf("%d",&n);
    m=1,dfs(m);
    printf("%lld\n",ans);
    return 0;
}