题目描述

现在有一棵二叉树,所有非叶子节点都有两个孩子。

在每个叶子节点上有一个权值(有$n$个叶子节点,满足这些权值为$1..n$的一个排列)。

可以任意交换每个非叶子节点的左右孩子。

要求进行一系列交换,使得最终所有叶子节点的权值按照中序遍历写出来,逆序对个数最少。

输入格式

第一行$n$,下面每行,一个数$x$。

如果$x==0$,表示这个节点非叶子节点,递归地向下读入其左孩子和右孩子的信息。

如果$x!=0$,表示这个节点是叶子节点,权值为$x$。

输出格式

一行,最少逆序对个数。

样例输入

3
0
0
3
1
2

样例输出

1

数据范围

对于$30%$的数据:$2<=n<=5000$。

对于$100%$的数据:$2<=n<=200000$。

菜鸡的咆哮

一个子树之内调换左右儿子,对子树之外的节点没有影响。

于是考虑$DFS$整棵树,对于一个节点的左右儿子,统计交换与不交换贡献的逆序对个数取最小值统计。

如何同时求出交换与不交换左右儿子情况下的逆序对数量?

可以在初始时对原树中的每个叶子结点建一棵动态开点权值线段树。

在DFS中访问完左右儿子后将它们的线段树合并成为父亲节点的线段树。

合并的过程中顺便求出横跨左右子树的逆序对个数。(没有横跨的在之前已经统计过了)。

讨论交换与不交换两种情况:

如果不交换,贡献的逆序对数为$sum[ls[rx]]\times sum[rs[lx]]$

如果交换,贡献的逆序对数为$sum[ls[lx]]\times sum[rs[rx]]$

$lx$为儿子线段树当前区间下标,$rx$为右儿子线段树当前节点下标。

让我们手动模拟一个样例:

b5cab524df4e14bc683f6990a7e68d49.jpg

代码

#include<bits/stdc++.h>
#define maxn 400005
#define ll long long
using namespace std;
int sum[20*maxn];
int ls[20*maxn];
int rs[20*maxn];
int n;
int tail;
ll ans;
ll ans1,ans2;
void update(int &k,int l,int r,int x){
    if(!k) k=++tail;
    sum[k]++;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(x<=mid) update(ls[k],l,mid,x);
    else update(rs[k],mid+1,r,x);
}
void merge(int &lx,int rx){
    if(!lx||!rx){lx=lx+rx;return;}
    sum[lx]+=sum[rx];
    ans1+=(ll)sum[rs[lx]]*sum[ls[rx]];
    ans2+=(ll)sum[ls[lx]]*sum[rs[rx]];    
    merge(ls[lx],ls[rx]);
    merge(rs[lx],rs[rx]);
}
void solve(int &x){
    int opt,ls,rs;
    x=0;
    scanf("%d",&opt);
    if(opt==0){
        solve(ls);solve(rs);
        ans1=ans2=0;
        x=ls;merge(x,rs);
        ans+=min(ans1,ans2);
    }
    else update(x,1,n,opt);
}
int main(){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    scanf("%d",&n);
    int t=0;
    solve(t); 
    printf("%lld\n",ans);
    return 0;
}