【BZOJ2212】【POI2011】【XSY2014】Tree Rotation（线段树合并）

输入格式真的毒瘤

权值线段树合并。

我们先对每一个叶子建一棵权值线段树，并把它自己的权值插入到里面。

我们不妨设原树中当前节点为 \(u\)，爸爸 \(fa\)，左儿子 \(lc\)，右儿子 \(rc\)，那么显然这棵树中的逆序对分为 \(3\) 个部分：\(lc\) 里的逆序对，\(rc\) 里的逆序对和跨 \(lc\) 和 \(rc\) 的逆序对。

而我们现在已经把 \(lc\) 里的逆序对和 \(rc\) 里的逆序对算好了，现在需要求出跨 \(lc\) 和 \(rc\) 的逆序对，也就是合并 \(lc\) 和 \(rc\) 。然后我们发现，无论 \(lc\) 内的子树怎么换来换去，\(rc\)内的子树怎么换来换去，都是对跨 \(lc\) 和 \(rc\) 的逆序对个数没有影响的。

同理，无论我们交不交换 \(lc\) 和 \(rc\)，对 \(fa\) 那一层的合并也是没有影响的。

所以对于跨 \(lc\) 和 \(rc\) 的逆序对，我们分交换 \(lc\)、\(rc\) 和不交换的情况算出两种情况的逆序对个数，再取较小值就好了。

我们遍历两棵权值线段树来暴力合并两棵权值线段树。

那么对于 \(lc\) 和 \(rc\) 权值线段树中同一位置的点 \(a\)、\(b\)，若不交换 \(lc\) 和 \(rc\)，显然 \(lc\) 中的点的编号（这里的编号是指前序遍历的先后顺序）肯定都在 \(rc\) 前，\(a\) 右儿子的权值必定大于 \(b\) 左儿子的权值，所以 \(size[ch[a][1]]*size[ch[b][0]]\) 就是这一位置的答案了。

同理，如果交换 \(lc\) 和 \(rc\)，这一位置的答案就是 \(size[ch[a][0]]*size[ch[b][1]]\)。

最后合并完统计答案即可。

代码如下：

#include<bits/stdc++.h>

#define N 200010
#define int long long

using namespace std;

struct Tree
{
	int ch[2],size;
}t[N<<5];

int n,tot,ans,num1,num2;

int update(int l,int r,int val)
{
	int u=++tot;
	t[u].size=1;
	if(l==r) return u;
	int mid=(l+r)>>1;
	if(val<=mid) t[u].ch[0]=update(l,mid,val);
	else t[u].ch[1]=update(mid+1,r,val);
	return u;
}

int merge(int a,int b,int l,int r)//把b合并至a
{
	if(!a||!b) return a+b;
	if(l==r)
	{
		t[a].size+=t[b].size;
		return a;
	}
	num1+=t[t[a].ch[1]].size*t[t[b].ch[0]].size;//不交换的答案
	num2+=t[t[b].ch[1]].size*t[t[a].ch[0]].size;//交换后的答案
	int mid=(l+r)>>1;
	t[a].ch[0]=merge(t[a].ch[0],t[b].ch[0],l,mid);
	t[a].ch[1]=merge(t[a].ch[1],t[b].ch[1],mid+1,r);
	t[a].size+=t[b].size;
	return a;
}

int dfs()
{
	int u,val;
	scanf("%lld",&val);
	if(!val)
	{
		int lc=dfs(),rc=dfs();
		num1=num2=0;
		u=merge(lc,rc,1,n);
		ans+=min(num1,num2);//ans加上较小值
	}
	else u=update(1,n,val);
	return u;
}

signed main()
{
	scanf("%lld",&n);
	dfs();
	printf("%lld\n",ans);
	return 0;
}