【BZOJ2212】【POI2011】【XSY2014】Tree Rotation（線段樹合并）

輸入格式真的毒瘤

權值線段樹合并。

我們先對每一個葉子建一棵權值線段樹，并把它自己的權值插入到裡面。

我們不妨設原樹中目前節點為 u u u，爸爸 f a fa fa，左兒子 l c lc lc，右兒子 r c rc rc，那麼顯然這棵樹中的逆序對分為 3 3 3 個部分： l c lc lc 裡的逆序對， r c rc rc 裡的逆序對和跨 l c lc lc 和 r c rc rc 的逆序對。

而我們現在已經把 l c lc lc 裡的逆序對和 r c rc rc 裡的逆序對算好了，現在需要求出跨 l c lc lc 和 r c rc rc 的逆序對，也就是合并 l c lc lc 和 r c rc rc 。然後我們發現，無論 l c lc lc 内的子樹怎麼換來換去， r c rc rc内的子樹怎麼換來換去，都是對跨 l c lc lc 和 r c rc rc 的逆序對個數沒有影響的。

同理，無論我們交不交換 l c lc lc 和 r c rc rc，對 f a fa fa 那一層的合并也是沒有影響的。

是以對于跨 l c lc lc 和 r c rc rc 的逆序對，我們分交換 l c lc lc、 r c rc rc 和不交換的情況算出兩種情況的逆序對個數，再取較小值就好了。

我們周遊兩棵權值線段樹來暴力合并兩棵權值線段樹。

那麼對于 l c lc lc 和 r c rc rc 權值線段樹中同一位置的點 a a a、 b b b，若不交換 l c lc lc 和 r c rc rc，顯然 l c lc lc 中的點的編号（這裡的編号是指前序周遊的先後順序）肯定都在 r c rc rc 前， a a a 右兒子的權值必定大于 b b b 左兒子的權值，是以 s i z e [ c h [ a ] [ 1 ] ] ∗ s i z e [ c h [ b ] [ 0 ] ] size[ch[a][1]]*size[ch[b][0]] size[ch[a][1]]∗size[ch[b][0]] 就是這一位置的答案了。

同理，如果交換 l c lc lc 和 r c rc rc，這一位置的答案就是 s i z e [ c h [ a ] [ 0 ] ] ∗ s i z e [ c h [ b ] [ 1 ] ] size[ch[a][0]]*size[ch[b][1]] 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;
}