题解 P3521 【[POI2011]ROT-Tree Rotations】

正如前面大佬们所说的： 权值线段树和线段树合并。

对于任意一个节点，交换左右子树对当前节点和前面的所有节点没有影响。

因为这是前序遍历：根节点->左子树->右子树。可以看到，交换左右子树对前面的节点无影响。

我们要求的是逆序对最小，对于一个节点，逆序对有三种：

• 在左子树中。
• 在右子树中。
• 跨越了左右子树。

我们清楚，交换子树只会对第三种情况产生影响。因此，我们只需要在合并线段树的过程中统计交换子树的逆序对个数u和不交换子树的逆序对个数v，取 min(u,v) 累加到答案中就行了。

现在的问题是如何找第三种情况下的逆序对。

上图：

用p表示左子树，q表示右子树。ls表示左子节点，rs表示右子节点。

很明显，对于除了叶节点的每一个节点：

1. 如果不交换： u+=[p.rs].size*[q.ls].size 。
2. 如果交换： v+=[p.ls].size*[q.rs].size。

重点：每一次合并线段树时，递归到除了叶节点的所有节点，都要累加逆序对个数u,v。

看图模拟一边很容易就明白了。

比如，递归到[1~4]这个节点时，累加u:我们只累加了3、4对1、2行成的 2*2=4 组逆序对。但是继续向下递归到[3~4]时，4对3还有一组逆序对。

因此，递归到除了叶节点的所有节点时，都要进行累加 u,v 的操作。

讲完了。

补充------空间复杂度：

我们对每个叶节点都需要进行建树操作，该建树操作的值域是 [1,n] ，而我们每次建树都得到一条链，这条链的长度就是 logn ，因为有 logn 层。 考虑极限情况，有大约 n 个叶节点，那么总的空间就是 nlogn 。

注意： 线段树合并不需要新开节点。

通俗易懂的代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
int n,top;//top：创建节点个数 
ll ans,u,v;//u,v：逆序对个数 
struct Tree{
    int ls,rs,size;
}da[22*N];//N*logN的空间 

int in(){//快读 
    int x=0;char ch=getchar();
    while(ch>'9'||ch<'0') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}

int update(int l,int r,int val){//创建权值线段树 
    int pos=++top;
    da[pos].size++;
    if(l==r) return pos;
    int mid=(l+r)>>1;
    if(val<=mid) da[pos].ls=update(l,mid,val);
    else da[pos].rs=update(mid+1,r,val);
    return pos;
}

int merge(int p,int q,int l,int r){//合并线段树 
    if(!q||!p) return (!p)?q:p;//如果有节点为空，返回另一个节点 
    if(l==r){ da[p].size+=da[q].size; return p; }//叶节点，合并，返回 
    u+=(ll)da[da[p].rs].size*da[da[q].ls].size;//交换前 
    v+=(ll)da[da[p].ls].size*da[da[q].rs].size;//交换后 
    int mid=(l+r)>>1;
    da[p].ls=merge(da[p].ls,da[q].ls,l,mid);//继续合并左子节点 
    da[p].rs=merge(da[p].rs,da[q].rs,mid+1,r);//右子节点 
    da[p].size=da[da[p].ls].size+da[da[p].rs].size;//重置更新当前节点 
    return p;
} 

int dfs(){
    int pos,val=in();
    if(val==0){//不是叶节点 
        int ls=dfs(),rs=dfs();//ls:左子树的权值线段树的根节点，rs同理 
        u=0;v=0;//记得每次清零 
        pos=merge(ls,rs,1,n);//pos：合并后的权值线段树的根节点 
        ans+=min(u,v);//累加答案 
    }
    else pos=update(1,n,val);//叶节点，建树 
    return pos;//返回这颗权值线段树的根节点 
}

int main(){
    n=in();
    dfs();
    printf("%lld",ans);
    return 0;
}