【BZOJ3702】二叉树

  对每一个节点建一棵长度为n的线段树，记录该节点所在子树中有哪些数。

  因为旋转一棵子树的左右两个子树并不影响该子树中的数与其他数的相对位置关系，所以只需贪心地考虑是否要交换两棵子树。

  若左树中有n个数，右树中有m个数，未交换前有k对逆序对，交换后就变成了n*m-k个。取最小值即可。

  然后查询逆序对个数的时候顺便合并线段树。

  由于每个叶子节点建了一棵线段树，每棵树大小为log n，所以空间复杂度为n log n。

  合并线段树的过程中，因为线段树中每个节点最多经过n/(2^h)次（其中h表示该节点的深度），所以时间复杂度也是n log n的。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=200010;

struct Node
{
	Node *c[2];
	int sum;
	int l,r;
}root,Null,ID[maxn<<5];

int n;
int cnt;
LL ans;

#define ls x->c[0]
#define rs x->c[1]

void Update(Node *x) {x->sum=ls->sum+rs->sum;}

void Build_New_Tree(Node *x,int v)
{
	x->sum=1;
	ls=rs=&Null;
	if (x->l==x->r) return;
	int mid=(x->l+x->r)>>1;
	if (v<=mid)
	{
		ls=&ID[cnt++];
		ls->l=x->l;
		ls->r=mid;
		Build_New_Tree(ls,v);
	}
	else
	{
		rs=&ID[cnt++];
		rs->l=mid+1;
		rs->r=x->r;
		Build_New_Tree(rs,v);
	}
}

LL Merge(Node *a,Node *b)
{
	LL res=0;
	res=(LL)a->c[1]->sum*b->c[0]->sum;
	if (a->c[0]!=&Null && b->c[0]!=&Null) res+=Merge(a->c[0],b->c[0]);
		else if (a->c[0]==&Null && b->c[0]!=&Null) a->c[0]=b->c[0];
	if (a->c[1]!=&Null && b->c[1]!=&Null) res+=Merge(a->c[1],b->c[1]);
		else if (a->c[1]==&Null && b->c[1]!=&Null) a->c[1]=b->c[1];
	Update(a);
	return res;
}

Node *Solve()
{
	int v;
	scanf("%d",&v);
	if (v)
	{
		Node *x=&ID[cnt++];
		x->l=1;x->r=n;
		Build_New_Tree(x,v);
		return x;
	}
	else
	{
		Node *x=Solve();
		Node *y=Solve();
		LL xn=x->sum,yn=y->sum;
		LL res=Merge(x,y);
		if (res>xn*yn-res) res=xn*yn-res;
		ans+=res;
		return x;
	}
}

#undef ls
#undef rs

int main()
{
	freopen("test.in","r",stdin);
	scanf("%d",&n);
	Null.c[0]=Null.c[1]=&Null;
	Null.sum=0;
	(void)Solve();
	printf("%lld\n",ans);
	return 0;
}