思路：

　　区间合并线段树的题，第一次写，对于一颗子树，无论这个子树怎么交换，都不会对其他子树的逆序对造成影响，所以就直接算逆序对就好。

　　注意叶子节点是1到n的全排列，所以每个权值都只会出现1次，合并很好写。

　　注意动态开点，最多n个叶子节点，然后每次查询用到log个子树节点，（这句话似乎有语病）所以要开nlogn的空间。

#include
      
       #define clr(a,b) memset(a,b,sizeof(a))#define fpn() freopen("simple.in","r",stdin)using namespace std;typedef long long ll;const int inf=0x3f3f3f3f;const int maxn=200005;int n,q,tot,r,k,cnt;int R[maxn*30],rt[maxn*30],L[maxn*30],val[maxn*30],ch[maxn*30][2];ll sum[maxn*30],ans,anl,anr;void read(int &r){    r=++tot;    scanf("%d",&val[r]);    if(!val[r]){        read(ch[r][0]);        read(ch[r][1]);    }}void pushup(int x){    sum[x]=sum[L[x]]+sum[R[x]];}void insert(int &x,int l,int r,int p){    x=++cnt;    int mid=(l+r)>>1;    if(l==r){        sum[x]=1;        return;    }    if(p<=mid)insert(L[x],l,mid,p);    else insert(R[x],mid+1,r,p);    pushup(x);}int merge(int x,int y){    if(!x)return y;    if(!y)return x;    anl+=sum[L[x]]*sum[R[y]];    anr+=sum[L[y]]*sum[R[x]];    L[x]=merge(L[x],L[y]);    R[x]=merge(R[x],R[y]);    pushup(x);    return x;}ll dfs(int x){    ll ans=0;    if(!val[x]){            ans+=dfs(ch[x][0])+dfs(ch[x][1]);        anl=anr=0;        rt[x]=merge(rt[ch[x][0]],rt[ch[x][1]]);        ans+=min(anl,anr);    }else{        insert(rt[x],1,n,val[x]);    }    return ans;}int main(){    scanf("%d",&n);    read(r);    ans=dfs(1);    cout<
       
        <