《程序设计基础二》类的设计部分练习题目:1432--1446,运算符重载部分练习题目:1447--1461

Problem 1997. -- 逆序对

1997: 逆序对

Time Limit: 2 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 4  Accepted: 1
[Submit][Status][Web Board]

Description

Alice是一个让人非常愉跃的人!他总是去学习一些他不懂的问题,然后再想出许多稀奇古怪的题目。这几天,Alice又沉浸在逆序对的快乐当中,他已近学会了如何求逆序对对数,动态维护逆序对对数等等题目,他认为把这些题让你做简直是太没追求了,于是,经过一天的思考和完善,Alice终于拿出了一道他认为差不多的题目:
有一颗2n-1个节点的二叉树,它有恰好n个叶子节点,每个节点上写了一个整数。如果将这棵树的所有叶子节点上的数从左到右写下来,便得到一个序列a[1]…a[n]。现在想让这个序列中的逆序对数量最少,但唯一的操作就是选树上一个非叶子节点,将它的左右两颗子树交换。他可以做任意多次这个操作。求在最优方案下,该序列的逆序对数最少有多少。
Alice自己已近想出了题目的正解,他打算拿来和你分享,他要求你在最短的时间内完成。

Input

多组测试数据。每组数据格式如下。
第一行一个整数n。
下面每行,一个数x。
如果x=0,表示这个节点非叶子节点,递归地向下读入其左孩子和右孩子的信息,如果x≠0,表示这个节点是叶子节点,权值为x。
1 <= n <= 200000,0 <= a[i]<2^31

Output

每组输出一个整数,表示最少有多少逆序对。

Sample Input

3
0
0
3
1
2

Sample Output

1

[Submit][Status][Web Board]