「BZOJ3702」「FJ互测」二叉树

2014年7月24日4,6201

Description(tree.c/.cpp/.pas)

现在有一棵二叉树,所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有n个叶子节点,满足这些权值为1..n的一个排列)。可以任意交换每个非叶子节点的左右孩子。

要求进行一系列交换,使得最终所有叶子节点的权值按照中序遍历写出来,逆序对个数最少。

Input Format(tree.in)

第一行n

下面每行,一个数x

如果x==0,表示这个节点非叶子节点,递归地向下读入其左孩子和右孩子的信息,

如果x!=0,表示这个节点是叶子节点,权值为x。

Output Format(tree.out)

一行,最少逆序对个数。

Sample Input

3

0

0

3

1

2

Sample Output

1

Hint

对于30%的数据:2<=n<=5000。
对于100%的数据:2<=n<=200000。
由于评测机的系统栈实在呵呵……不想写人工栈而爆栈的神犇可以脑补一下你AC的场景
题解
先打了个暴力2333

对于一个非叶子节点,是否交换它的儿子对它之后的统计没有影响
统计每个点左右儿子是否交换,并暴力求出每个节点贡献的逆序对数Sum[i],求∑Sum[i] (30分)

考虑每个点维护一棵线段树,在每个非叶子结点直接合并线段树,然后顺便统计答案,动态开空间

这个合并怎么这么像左偏树

 

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
wycero Recent comment authors
  Subscribe  
提醒
wycero

orzhzw