[题解] poi 2011 Tree Rotations(线段树合并)

- 传送门 -

　http://main.edu.pl/en/archive/oi/18/rot
　http://main.edu.pl/en/user.phtml?op=zasoby (数据)

#Tree Rotations Memory limit: 64 MB

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 [题解] poi 2011 Tree Rotations(线段树合并) , such that in the corona .

[题解] poi 2011 Tree Rotations(线段树合并)
The original tree (on the left) with corona has two inversions. A single rotation gives a tree (on the right) with corona , 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.

Input

In the first line of the standard input there is a single integer [题解] poi 2011 Tree Rotations(线段树合并) () 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 () 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).

In tests worth at least 30% of the points it additionally holds that [题解] poi 2011 Tree Rotations(线段树合并) .

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.

Example

For the input data:
3
0
0
3
1
2

the correct result is:

Explanation of the example: Figure 1 illustrates the tree given in the example.

- 题意 -

　一颗二叉树, 保证非叶子节点一定有左右儿子, 叶子节点有权值(n个叶子节点, 满足权值是1-n的排列), 非叶子节点的左右儿子可以互换, 问任意互换后,遍历该树得到的序列中逆序对个数最少为多少.
　

- 思路 -

　自底层向上对每个节点动态开线段数, 表示该节点表示的区间内存在的点, 非叶子节点由它的两个儿子合并组成.
　一个节点的左右儿子各自的排列顺序对跨左右区间的逆序对个数是没有影响的, 所以每次合并时只要考虑让当前区间内逆序对尽量少,问题就转化为求逆序对的个数,这个可以用权值线段树乱搞,具体看代码.
　注意一点细节因为这题空间不够所以不能一次把底层线段树都开出来,而要一边对叶子节点开树一边合并并回收节点(然而还是开了玄学空间).
　
　细节见代码.
　

- 代码 -

#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N = 2e5 + 5;
const int M = 4e5 + 5;
const int H = N * 9; //玄学空间...

int RT[M], SUM[H], L[M], R[M], LS[H], RS[H];
int REC[H];
int n, sz, tot, tp, v;
ll c1, c2, ans;

void pu(int rt) {
	SUM[rt] = SUM[LS[rt]] + SUM[RS[rt]];
}

void build(int &rt, int l, int r, int k) {
	if (tp) rt = REC[tp--];
	else rt = ++tot;
	if (l == r) {
		SUM[rt] ++;
		return;
	}
	int mid = l + r >> 1;
	if (k <= mid) build(LS[rt], l, mid, k);
	else build(RS[rt], mid + 1, r, k);
	pu(rt);
}//动态开点

void recover(int x) {
	if (!x) return;
	REC[++tp] = x; LS[x] = RS[x] = SUM[x] = 0;
}//回收节点

int merge(int l, int r) {
	if (!l) return r;
	if (!r) return l;
	c1 += 1ll * SUM[RS[l]] * SUM[LS[r]];
	c2 += 1ll * SUM[LS[l]] * SUM[RS[r]];//权值线段树统计逆序对
	LS[l] = merge(LS[l], LS[r]);
	RS[l] = merge(RS[l], RS[r]);
	pu(l);
	recover(r);
	return l;
}

void solve(int rt) {
	scanf("%d", &v);
	if (v) {
		build(RT[rt], 1, n, v); //一边开点
		return;
	}
	L[rt] = ++sz; solve(L[rt]);
	R[rt] = ++sz; solve(R[rt]);
	c1 = c2 = 0;
	RT[rt] = merge(RT[L[rt]], RT[R[rt]]);//一边合并
	ans += min(c1, c2);
}

int main() {
	freopen("rot.in","r",stdin);
	freopen("rot.out","w",stdout);
	scanf("%d", &n);
	sz = 1;
	solve(1);
	printf("%lld
", ans);
}