题解 P3521 【[POI2011]ROT-Tree Rotations】
IC_QQQ
2019-05-13 20:57:35
正如前面大佬们所说的: **权值线段树**和**线段树合并**。
对于任意一个节点,交换左右子树对当前节点和前面的所有节点**没有影响**。
因为这是**前序遍历**:根节点->左子树->右子树。可以看到,交换左右子树**对前面的节点无影响**。
我们要求的是逆序对最小,对于一个节点,逆序对有三种:
+ 在左子树中。
+ 在右子树中。
+ 跨越了左右子树。
我们清楚,交换子树只会对**第三种情况**产生影响。因此,我们只需要在**合并线段树**的过程中统计交换子树的逆序对个数u和不交换子树的逆序对个数v,取 **min(u,v)** 累加到答案中就行了。
现在的问题是如何找**第三种情况下的逆序对**。
上图:
![](https://i.loli.net/2019/05/13/5cd96945b450241844.png)
用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$ 。
注意: **线段树合并不需要新开节点**。
### 通俗易懂的代码:
```cpp
#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;
}
```