[bzoj3702/2212][Poi2011]二叉树/Tree Rotations_线段树

二叉树 Tree Rotations bzoj-3702 bzoj-2212 Poi-2011

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

注释：$2\le n \le 2\cdot 10^5$。

想法：显然，对于一个节点的两个儿子lson和rson，无论lson和rson内部如何操作，任何两个数x和y，满足lson是x的祖先，rson是y的祖先且x>y，按照这样构成的逆序对是不会因为内部操作而消失的，同样地，也不会平白无故增加。所以一个节点pos的操作与不操作是独立的，我们只需要将当前当前节点的两颗子树之间的逆序对数维护到最小，显然就是最优解。这样我们对每一个点维护左右逆序对数和区间和，然后自底向上操作。这个过程用线段树模拟。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

using namespace std;

#define N 400010

typedef long long ll;

int n,sz,seg;

ll ans,cnt1,cnt2;

int v[N],l[N],r[N],root[N];

int sum[N*10],ls[N*10],rs[N*10];

void readtree(int pos)

{

	scanf("%d",&v[pos]);

	if(!v[pos])

	{

		l[pos]=++sz;

		readtree(l[pos]);

		r[pos]=++sz;

		readtree(r[pos]);

	}

}

void pushup(int pos)

{

	sum[pos]=sum[ls[pos]]+sum[rs[pos]];

}

void build(int &pos,int l,int r,int val)

{

	if(!pos)pos=++seg;

	if(l==r){sum[pos]=1;return;}

	int mid=(l+r)>>1;

	if(val<=mid)build(ls[pos],l,mid,val);

	else build(rs[pos],mid+1,r,val);

	pushup(pos);

}

int merge(int x,int y)

{

	if(!x)return y;

	if(!y)return x;

	cnt1+=(ll)sum[rs[x]]*sum[ls[y]];

	cnt2+=(ll)sum[ls[x]]*sum[rs[y]];

	ls[x]=merge(ls[x],ls[y]);

	rs[x]=merge(rs[x],rs[y]);

	pushup(x);

	return x;

}

void solve(int pos)

{

	if(!pos)return;

	solve(l[pos]);solve(r[pos]);

	if(!v[pos])

	{

		cnt1=cnt2=0;

		root[pos]=merge(root[l[pos]],root[r[pos]]);

		ans+=min(cnt1,cnt2);

	}

}

int main()

{

	scanf("%d",&n);

	++sz;

	readtree(1);

	for(int i=1;i<=sz;i++)

		if(v[i])build(root[i],1,n,v[i]);

	solve(1);

	printf("%lld\n",ans);

	return 0;

}

小结：超级喜欢的一道题，先从小引理入手，然后再进行一系列思考。