[bzoj3702] 二叉树

　　一个节点的儿子是否交换，不会影响到它和兄弟节点间的逆序对数。

　　所以每次合并线段树的时候算一下交换与不交换的逆序对数，然后选个较小值就行了。

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #define ll long long

 using namespace std;

 const int maxn=,mxnode=*;

 int lc[mxnode],rc[mxnode],sz[mxnode],tot;

 int ls[maxn],rs[maxn],size[maxn],mp[maxn],tt,rt[maxn];

 int i,j,k,n,m,presz,P,id,root;

 ll num0,num1,ans;

 int ra;char rx;

 inline int read(){

     rx=getchar(),ra=;

     while(rx<''||rx>'')rx=getchar();

     while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;

 }

 int merge(int a,int b){

     if(!b){presz+=sz[a];return a;}

     if(!a){num0+=1LL*sz[b]*presz;return b;}

     sz[a]+=sz[b];

     rc[a]=merge(rc[a],rc[b]),lc[a]=merge(lc[a],lc[b]);

     return a;

 }

 void build(int &x,int a,int b){

     x=++tot,sz[x]=;

     if(a==b)return;

     int mid=a+b>>;

     if(P<=mid)build(lc[x],a,mid);else build(rc[x],mid+,b);

 }

 void in(int &x){

     x=++tt,id=read();

     if(id)mp[x]=id,size[x]=;else

         in(ls[x]),in(rs[x]),size[x]=size[ls[x]]+size[rs[x]];

 }

 void dfs(int x){

     if(size[x]==){P=mp[x],build(rt[x],,n);return;}

     dfs(ls[x]),dfs(rs[x]),

     presz=num0=,rt[x]=merge(rt[ls[x]],rt[rs[x]]);

     num1=1LL*size[ls[x]]*size[rs[x]]-num0;

 //  printf("  %d %lld %lld\n",x,num0,num1);

     ans+=min(num0,num1);

 }

 int main(){

     n=read();

     in(root);//printf("cnt: %d\n",cnt);

     dfs();

     printf("%lld\n",ans);

     return ;

 }