BZOJ2212: [Poi2011]Tree Rotations 线段树合并

2212: [Poi2011]Tree Rotations
Time Limit: 20 Sec Memory Limit: 259 MB
Submit: 1501 Solved: 596
[Submit][Status][Discuss]
Description

现在有一棵二叉树，所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有n个叶子节点，满足这些权值为1..n的一个排列)。可以任意交换每个非叶子节点的左右孩子。
要求进行一系列交换，使得最终所有叶子节点的权值按照遍历序写出来，逆序对个数最少。

Input

第一行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
0
0
3
1
2

Sample Output
1

题解：
首先考虑树上某一个节点，这个节点的左子树与右子树对答案的贡献只有两种情况要考虑——交换或不交换，至于两棵子树内部怎么搞，和这一部分是没有关系的。
考虑启发式合并来维护每个子树…$O(n log^2n)$，T啦
这个时候就要请出线段树合并了。考虑维护每个子树的权值线段树。这个权值线段树显然是可以动态开点并且合并的。考虑权值线段树上，每个点左右子树对两种情况答案的贡献：将左子树上权值线段树的点归于集合1，右子树归于集合2，权值线段树上某一点的左右子树对答案1（不交换）的贡献为：左子树中的二号点个数 * 右子树中的一号点个数；对答案2（交换）的贡献为：左子树中的一号点个数 * 右子树中的二号点个数。
这个点的左右子树对这个点答案的贡献为min（答案1，答案2）+左右儿子的答案。
根节点的答案即为要求的答案。

代码：

#include
#include
#include
#include
#include
using std::cin;
using std::cout;
using std::min;
using std::endl;
const int maxn = 200000 + 5;
struct node {int msg,lson,rson,first;long long ans;
} tree[maxn * 19];
node M_tree[maxn * 19];
int first[maxn * 19];
int n;
int root;
int cnt;
int build() {int step = ++cnt;int x;scanf("%d",&x);if(x != 0) {tree[step].msg = x;}else {tree[step].lson = build();tree[step].rson = build();}return step;
}
int add(int l,int r,int pos) {int step = ++cnt;if(l == r) {M_tree[step].msg = 1;return step;}int mid = (l + r) / 2;if(pos <= mid)M_tree[step].lson = add(l , mid , pos);elseM_tree[step].rson = add(mid + 1 , r , pos);M_tree[step].msg = 1;return step;
}
long long ans1 , ans2;
int merge(int step1,int step2,int l,int r) {int step = ++cnt;M_tree[step].msg = M_tree[step1].msg + M_tree[step2].msg;if(l == r) return step;ans1 += (long long)M_tree[M_tree[step1].lson].msg * (long long)M_tree[M_tree[step2].rson].msg;ans2 += (long long)M_tree[M_tree[step2].lson].msg * (long long)M_tree[M_tree[step1].rson].msg;int mid = (l + r) >> 1;if(M_tree[step1].lson && M_tree[step2].lson) M_tree[step].lson = merge(M_tree[step1].lson , M_tree[step2].lson , l , mid);else if(M_tree[step1].lson) M_tree[step].lson = M_tree[step1].lson;else if(M_tree[step2].lson) M_tree[step].lson = M_tree[step2].lson;if(M_tree[step1].rson && M_tree[step2].rson) M_tree[step].rson = merge(M_tree[step1].rson , M_tree[step2].rson , mid + 1 , r);else if(M_tree[step1].rson) M_tree[step].rson = M_tree[step1].rson;else if(M_tree[step2].rson) M_tree[step].rson = M_tree[step2].rson;return step;
}
void dfs(int step) {if(tree[step].msg != 0) {tree[step].first = add(1 , n , tree[step].msg);return;}if(tree[step].lson) dfs(tree[step].lson);if(tree[step].rson) dfs(tree[step].rson);if(tree[step].lson != 0 && tree[step].rson == 0) {tree[step].ans = tree[tree[step].lson].ans;tree[step].first = tree[tree[step].lson].first;return;}if(tree[step].rson != 0 && tree[step].lson == 0) {tree[step].ans = tree[tree[step].rson].ans;tree[step].first = tree[tree[step].rson].first;return;}ans1 = 0;ans2 = 0;tree[step].first = merge(tree[tree[step].lson].first , tree[tree[step].rson].first , 1 , n);tree[step].ans += min(ans1 , ans2);tree[step].ans += tree[tree[step].lson].ans + tree[tree[step].rson].ans;
}
int main() {cin>>n;root = build();cnt = 0;dfs(root);printf("%lld\n",tree[root].ans);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！