题解 P3521 【[POI2011]ROT-Tree Rotations】
Unordered_OIer
·
·
题解
P3521 题解
题意
一棵二叉树，所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有 n 个叶子节点，满足这些权值为 1 ...... n 的一个排列)。可以任意交换每个非叶子节点的左右孩子。
要求进行交换使最终所有叶子节点的权值按遍历序写出来逆序对个数最少。
建模
很显然内部结构不会影响逆序对个数，因此只需要统计每个节点左右子树之间的逆序对即可，于是：
ans=\sum\limits_{u=1}^{2n-1}\text{Count}(x,y)|x \in \text{ls}(u),y \in \text{rs}(u),a_x>a_y
其中 \text{ls}(u),\text{rs}(u) 分别代表 u 的左儿子和右儿子。
那么就以输入的 dfs 序计算 u 即可，接下来就是解决 x,y 。
-
暴力枚举 x,y
复杂度 \Theta(|\text{ls}(u)||\text{rs}(u)|)=\Theta(n^2) 。
-
归并排序
复杂度 \Theta(|\text{ls}(u)|+|\text{rs}(u)|)=\Theta(n \log n)\ /\ \Theta(n^2) ，因为树的结构给定，不能保证归并排序不退化。
那么我们就可以从值域的角度考虑，合并左右子树 x,y 的计数器数组 C_x,C_y 同样也能累计逆序对数。
此时：
ans(u)=\sum\limits_{i=1}^nC_x(i) \times \sum\limits_{j=1}^{i-1}C_y(j)
C_{x+y}(i)=C_x(i)+C_y(i)
## 优化
但是有一个问题就是这样做复杂度还没变。
一种解决办法就是启发式合并 $+\texttt{ BIT}$ ，复杂度 $\Theta(n (\log n)^2)$ 。
我们发现，对于一个子树 $u$ ， $C_u$ 只有 $\text{size}(u)$ 个位置非 $0$ ，如果遍历整个计数器就很浪费。
这种情况下对于每一个 $u$ 都进行标准的离散化显然非常亏。
于是，我们就可以想到**动态开点线段树**。
### 动态开点线段树
大致的说就是一次不把整个线段树建起来，而是根据输入只建一部分节点，剩下的那些用不到的节点就先不建。而需要注意的一个地方就是这样**动态开点**后 $x$ 的**左右儿子编号**不再是 $2x,2x+1$ 了，需要用一个单独的数组进行存储。
于是我们就要在原树的每个 $C_u$ 上建一个**动态开点权值线段树**，父线段树就是合并左右子线段树，即：
$$ans(u)=\sum\limits_{i=1}^nsz_x(\text{rs}(i)) \times sz_y(\text{ls}(i))$$
其中 $i$ 是权值线段树节点编号， $sz$ 是权值线段树的目标函数。
然后就可以快乐地写代码啦~
## Code
```cpp
#include<bits/stdc++.h>
#define N 抄袭差评
using namespace std;
typedef long long ll;
struct node{ll left_son,right_son,siz;}
segment_tree[N*30];
ll n,tot,ans,ans1,ans2;
ll create_Tree(ll l,ll r,ll x)
{
segment_tree[++tot].siz=1;
if(l==r)
return tot;
ll mid=(l+r)>>1,now=tot;
if(x<=mid)
segment_tree[now].left_son=create_Tree(l,mid,x);
else segment_tree[now].right_son=create_Tree(mid+1,r,x);
return now;
}
void combine_Tree(ll l,ll r,ll x,ll y)
{
if(l==r)
segment_tree[x].siz+=segment_tree[y].siz;
ll mid=(l+r)>>1;
ans1+=1ll*segment_tree[segment_tree[x].right_son].siz*segment_tree[segment_tree[y].left_son].siz;
ans2+=1ll*segment_tree[segment_tree[x].left_son].siz*segment_tree[segment_tree[y].right_son].siz;
if(segment_tree[y].left_son)
{
if(segment_tree[x].left_son)
combine_Tree(l,mid,segment_tree[x].left_son,segment_tree[y].left_son);
else
segment_tree[x].left_son=segment_tree[y].left_son;
}
if(segment_tree[y].right_son)
{
if(segment_tree[x].right_son)
combine_Tree(l,mid,segment_tree[x].right_son,segment_tree[y].right_son);
else
segment_tree[x].right_son=segment_tree[y].right_son;
}
segment_tree[x].siz=segment_tree[segment_tree[x].left_son].siz
+segment_tree[segment_tree[x].right_son].siz;
}
ll solve(){
ll v;v=read();
if(v)
return create_Tree(1,n,v);
ll x=solve(),y=solve();
ans1=ans2=0;
combine_Tree(1,n,x,y);
ans+=min(ans1,ans2);
return x;
}
int main(){
scanf("%lld",&n);
solve();
return 0;
}//缩进有些奇怪
```