2018.07.07 BZOJ2212: Poi2011Tree Rotations（線段樹合并）

2212: [Poi2011]Tree Rotations

Time Limit: 20 Sec Memory Limit: 259 MB

Description

Byteasar the gardener is growing a rare tree called Rotatus Informatikus. It has some interesting features: The tree consists of straight branches, bifurcations and leaves. The trunk stemming from the ground is also a branch. Each branch ends with either a bifurcation or a leaf on its top end. Exactly two branches fork out from a bifurcation at the end of a branch - the left branch and the right branch. Each leaf of the tree is labelled with an integer from the range . The labels of leaves are unique. With some gardening work, a so called rotation can be performed on any bifurcation, swapping the left and right branches that fork out of it. The corona of the tree is the sequence of integers obtained by reading the leaves’ labels from left to right. Byteasar is from the old town of Byteburg and, like all true Byteburgers, praises neatness and order. He wonders how neat can his tree become thanks to appropriate rotations. The neatness of a tree is measured by the number of inversions in its corona, i.e. the number of pairs（I,j）, (1< = I < j < = N )

such that(Ai>Aj) in the corona(A1,A2,A3…An). The original tree (on the left) with corona(3,1,2) has two inversions. A single rotation gives a tree (on the right) with corona(1,3,2), which has only one inversion. Each of these two trees has 5 branches. Write a program that determines the minimum number of inversions in the corona of Byteasar’s tree that can be obtained by rotations.

現在有一棵二叉樹，所有非葉子節點都有兩個孩子。在每個葉子節點上有一個權值(有n個葉子節點，滿足這些權值為1…n的一個排列)。可以任意交換每個非葉子節點的左右孩子。

要求進行一系列交換，使得最終所有葉子節點的權值按照周遊序寫出來，逆序對個數最少。

Input

In the first line of the standard input there is a single integer (2< = N < = 200000) that denotes the number of leaves in Byteasar’s tree. Next, the description of the tree follows. The tree is defined recursively: if there is a leaf labelled with ()(1<=P<=N) at the end of the trunk (i.e., the branch from which the tree stems), then the tree’s description consists of a single line containing a single integer , if there is a bifurcation at the end of the trunk, then the tree’s description consists of three parts: the first line holds a single number , then the description of the left subtree follows (as if the left branch forking out of the bifurcation was its trunk), and finally the description of the right subtree follows (as if the right branch forking out of the bifurcation was its trunk).

第一行n，下面每行，一個數x

如果x==0，表示這個節點非葉子節點，遞歸地向下讀入其左孩子和右孩子的資訊，如果x!=0，表示這個節點是葉子節點，權值為x

1<=n<=200000

Output

In the first and only line of the standard output a single integer is to be printed: the minimum number of inversions in the corona of the input tree that can be obtained by a sequence of rotations.

一行，最少逆序對個數

Sample Input

3

3

1

2

Sample Output

1

今天自學的新姿勢：線段樹合并，一個美（簡）妙（單）的東西。這應該算是線段樹合并的一道入門題目了。

那麼我們先講講線段樹合并是什麼吧。_

相信各位大佬對正常形态的線段樹都已經很了解了，也就是對于一些可以進行區間合并的運算利用以空間換時間的思想來将原本是 O （ n ） O（n） O（n）和 O （ 1 ） O（1） O（1）的詢問和修改都平均成了 O （ l o g n ） O（logn） O（logn）的。

但是！一般情況下不一定能這麼做，因為并不是每一道題都允許我們可以高效的維護區間資訊。怎麼解決這個問題？線段樹合并。

我們知道，當一顆線段樹根節點的取值範圍被确定之後，這棵樹的最終形态也随之确定了。這樣的話，對于兩顆根節點取值範圍相同的線段樹，我們可以采用類似于左偏堆的啟發式合并的方法合并這兩顆線段樹。合并的流程大概分個三步。

1. a,b兩顆線段樹的目前節點有一個沒有元素，直接傳回非空的一個。
2. a,b兩顆線段樹都通路到了葉節點，直接合并葉節點然後傳回。
3. 先分别将a,b兩顆線段樹的左右兒子合并，然後将兩顆合并後的樹連接配接起來。

從上述流程中可以看出，兩顆線段樹的合并的時間複雜度是基于它們的公共的節點數的。是以不難想到，當 1 − &gt; n 1-&gt;n 1−>n形成的線段樹依次合并時，時間複雜度最高為 O （ n l o g n ） O（nlogn） O（nlogn），是以可以發現我們使用這種線段樹合并的方法實際複雜度是有保障的，然後我們可以對比一下 t r e a p treap treap的合并和線段樹合并，平衡樹的啟發式合并的時間複雜度是 O （ n l o g n 2 ） O（nlogn^2） O（nlogn2）的，而線段樹合并卻是 O （ n l o g n ） O（nlogn） O（nlogn）的，這樣看來，用線段樹合并代替平衡樹的啟發式合并（如果題目允許的話）是可以起到給時間複雜度降階的作用的。

s o so so h o w how how t o to to w r i t e write write t h e the the c o d e code code?

合并部分的代碼如下（這份代碼與這道題有關）：

inline int merge(int x,int y){
	if(!x||!y)return x+y;
	calc();
	son[x][0]=merge(son[x][0],son[y][0]);
	son[x][1]=merge(son[x][1],son[y][1]);
	pushup(x);
	return x;
}
           

其中 c a l c calc calc函數在不同的題目下實作不同。

說了這麼多，大家一定都有一個疑問，這線段樹合并到底有什麼用啊？

線段樹合并的優點：

• 所有操作都從上傳到下，便于持久化。
• 線段樹合并的時間複雜度相對平衡樹等複雜資料結構來說更優。
• 代碼實作簡單，思考難度低。

但切記線段樹合并并不是萬能的方法。

回到這道題上吧，怎麼做呢？

對于以 p p p為根的子樹，整顆子樹中的逆序對數隻與左子樹中的逆序對數，右子樹中的逆序對數，還有 ( x &gt; y ∣ x ϵ 左 子 樹 , y ϵ 右 子 樹 ) (x&gt;y|xϵ左子樹,y ϵ右子樹) (x>y∣xϵ左子樹,yϵ右子樹)的對數，由于前兩者可以遞歸處理，且不會因子樹位置的交換而改變，我們就隻用考慮最後一項的變化了，最後一項無非就是從 ( x &gt; y ∣ x ϵ 左 子 樹 , y ϵ 右 子 樹 ) (x&gt;y|xϵ左子樹,y ϵ右子樹) (x>y∣xϵ左子樹,yϵ右子樹)的對數變成了 ( x &gt; y ∣ x ϵ 右 子 樹 , y ϵ 左 子 樹 ) (x&gt;y|xϵ右子樹,y ϵ左子樹) (x>y∣xϵ右子樹,yϵ左子樹)的對數，這個我們用權值線段樹就可以處理了。

于是我們得到了時空複雜度均為 O （ n l o g n ） O（nlogn） O（nlogn）的一個優秀的算法。當然空間複雜度可以更加優秀，直接壓到 O （ n ） O（n） O（n）（由于本蒟蒻懶癌晚期沒寫）。

代碼如下：

#include<bits/stdc++.h>
#define ll long long
#define N 400005
#define MN 4000005
using namespace std;
int n,a[N],s[N][2],root,rt[N],sum[MN],son[MN][2],tot=0,cnt=0;
ll ans0,ans1,ans;
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar();
	return ans;
}
inline void build(int &p){
	p=++cnt;
	a[p]=read();
	if(a[p])return;
	build(s[p][0]);
	build(s[p][1]);
}
inline void pushup(int x){sum[x]=sum[son[x][0]]+sum[son[x][1]];}
inline void update(int &p,int l,int r,int v){
	if(!p)p=++tot;
	if(l==r){
		sum[p]=1;
		return;
	}
	int mid=(l+r)>>1;
	if(v<=mid)update(son[p][0],l,mid,v);
	else update(son[p][1],mid+1,r,v);
	pushup(p);
}
inline int merge(int x,int y){
	if(!x||!y)return x+y;
	ans0+=(ll)sum[son[x][1]]*(ll)sum[son[y][0]];
	ans1+=(ll)sum[son[x][0]]*(ll)sum[son[y][1]];
	son[x][0]=merge(son[x][0],son[y][0]);
	son[x][1]=merge(son[x][1],son[y][1]);
	pushup(x);
	return x;
}
inline void query(int p){
	if(a[p])return;
	query(s[p][0]),query(s[p][1]);
	ans0=ans1=0;
	rt[p]=merge(rt[s[p][0]],rt[s[p][1]]);
	ans+=min(ans0,ans1);
}
int main(){
	n=read();
	build(root);
	for(int i=1;i<=cnt;++i)
		if(a[i])update(rt[i],1,n,a[i]);
	query(root);
	printf("%lld",ans);
	return 0;
}