题意

现在有一棵二叉树，所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有n个叶子节点，满足这些权值为1..n的一个排列)。可以任意交换每个非叶子节点的左右孩子。
要求进行一系列交换，使得最终所有叶子节点的权值按照遍历序写出来，逆序对个数最少。

\(1 \leq n \leq 200000\)

分析

左儿子和右儿子内部的逆序对是不会相互影响的。
将两部分单独处理再考虑合并。
合并的时候需要判断左儿子在前还是右儿子在前
枚举节点较少的部分，二分查询另一部分中权值更大的数目（类似启发式合并）。
利用权值线段树计算。

每个节点的逆序对是左子树的逆序对的数量+右子树的逆序对数量+跨越子树的逆序对数量
我们交换子树更改的就是最后那个跨越子树的逆序对数量，那么：

• 如果我们交换了左右子树，跨越子树的逆序对数量为没交换时左子树中<mid的数的数量*右子树中>=mid的数的数量
• 如果我们没有交换左右子树，那么逆序对数量就是左子树中>=mid的数的数量*右子树中<mid的数的数量
  然后仔细考虑每一个数，发现它的逆序对被一种二分分治的方式计算出来了。
  然后我们向上传递信息。这一步用线段树合并即可。

时间复杂度\(O(N \log N)\)

代码

#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<ctime>
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<complex>
#pragma GCC optimize ("O0")
using namespace std;
template<class T> inline T read(T&x)
{
    T data=0;
    int w=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch==‘-‘)
            w=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        data=10*data+ch-‘0‘,ch=getchar();
    return x=data*w;
}
typedef long long ll;
const int INF=0x7fffffff;

const int MAXT=2e5*20;
int n;
int a[MAXT]; // edit 1
int r,ls[MAXT],rs[MAXT],idx;

void init(int&x)
{
    x=++idx;
    read(a[x]);
    if(a[x])
        return;
    init(ls[x]);
    init(rs[x]);
}

ll ans1,ans2,ans;

int root[MAXT],sz;
struct PreSegTree
{
    int L[MAXT],R[MAXT];
    int sum[MAXT];
    
    void pushup(int now)
    {
        sum[now]=sum[L[now]]+sum[R[now]];
    }
    
    void insert(int&now,int l,int r,int p)
    {
        if(!now)
            now=++sz;
        if(l==r)
        {
            sum[now]=1;
            return;
        }
        int mid=(l+r)>>1;
        if(p<=mid)
            insert(L[now],l,mid,p);
        else
            insert(R[now],mid+1,r,p);
        pushup(now);
    }
    
    int merge(int x,int y)
    {
        if(!x||!y)
            return x+y;
        ans1+=(ll)sum[R[x]]*sum[L[y]];
        ans2+=(ll)sum[L[x]]*sum[R[y]];
        L[x]=merge(L[x],L[y]);
        R[x]=merge(R[x],R[y]);
        pushup(x);
        return x;
    }
}T;

void solve(int x)
{
    if(a[x])
        return;
    solve(ls[x]);
    solve(rs[x]);
    ans1=ans2=0;
    root[x]=T.merge(root[ls[x]],root[rs[x]]);
    ans+=min(ans1,ans2);
}

int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    read(n);
    init(r);
    for(int i=1;i<=idx;++i)
        if(a[i])
            T.insert(root[i],1,n,a[i]);
    solve(r);
    printf("%lld\n",ans);
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

Hint

根据该二叉树的性质，跟题干中的树有关的数组都应该开到\(O(2N)\)。

BZOJ2212 [Poi2011]Tree Rotations

原文：https://www.cnblogs.com/autoint/p/9636227.html