学习线段树合并，以这道为契机

多谢博客

这里是通过对线段树合并时，顺手统计了对于一颗子树内，是否反转两种情况的逆序对数

这里只对代码进行详细分析，见注解好了

1 #include
     
       2 #include
      
        3 #define N 210000*30 4 #define ll long long 5 using namespace std; 6 int n,tmp,ls[N],rs[N],data[N],tot; 7 ll ans,res1,res2; 8 int newtree(int l,int r,int x){
   //树的区间是[l,r]，其中只有x有值 9     data[++tot]=1;10     if(l==r)return tot;11     int mid=(l+r)/2,node=tot;12     if(x<=mid)ls[node]=newtree(l,mid,x);13     else rs[node]=newtree(mid+1,r,x);14     return node;15 }16 int merge(int l,int r,int u,int v){
   //对于范围同是[l,r]的树u，v,进行合并并返回新树的树根标号17     if(!u||!v)return u+v;//若有一个树没了，以后的信息可以直接继承，且不会贡献逆序对18     if(l==r){19         data[++tot]=data[u]+data[v];20         return tot;21     }22     int mid=(l+r)/2,node=++tot;23     res1+=(ll)data[rs[u]]*data[ls[v]],res2+=(ll)data[ls[u]]*data[rs[v]];//在这里统计跨过mid的逆序对，剩下的分治统计24     ls[node]=merge(l,mid,ls[u],ls[v]);25     rs[node]=merge(mid+1,r,rs[u],rs[v]);26     data[node]=data[ls[node]]+data[rs[node]];//合并节点信息27     return node;28 }29 int dfs(){30     scanf("%d",&tmp);31     if(tmp)return newtree(1,n,tmp);//建一颗只有tmp一个节点的线段树，并返回树根标号32     int node=merge(1,n,dfs(),dfs());33     ans+=min(res1,res2);//选择决策中较优的那个34     res1=res2=0;35     return node;36 }37 int main(){38     scanf("%d",&n);39     dfs();//递归读入加处理40     printf("%lld",ans);41     return 0;42 }