波蘭人太神秘了，竟能出出來如此題目。

題意

給一棵樹（讀入不太尋常，這個容易處理，忽略不計）, 每個葉子節點有一個權值，我們可以選擇交換一些節點的左右子樹（保證是二叉樹，且要么是葉子要么左右子樹都存在）。

經過交換后，跑前序遍歷，求最小化的逆序對數量。

大小不好說，大概是 1e6 左右。

做法

我們發現交換子樹這個操作似乎并不會影響其他的節點，因為是先序遍歷。

所以我們僅僅需要考慮內部新增的情況，考慮遞歸統計答案。

對于一個子樹，答案分三種：左子樹中，右子樹中，一左一右。

前兩者在子樹中已經算過，只需要考慮第三種。

我們需要快速計算左子樹對于右子樹能產生的逆序隊數量。

說到逆序對，我們就會想到各種各樣的數據結構，突然想到這個東西似乎可以使用線段樹統計。

如果有兩棵結構相同的權值線段樹中的對應節點 x, y 會給出 tr[tr[x].rc].siz*tr[tr[y].lc].siz 的貢獻。

調轉過來同理，我們就可以使用線段樹合并進行統計。

代碼↓

#include <bits/stdc++.h>
using namespace std;
const int MN=4e6+116;
struct Node{
	int lc, rc, siz;
}tr[MN];
void pushup(int k){
	tr[k].siz=tr[tr[k].lc].siz+tr[tr[k].rc].siz;
}
int tottt=0, root[MN];
long long ans=0, u, v;
int update(int k, int pos, int l, int r){
	if(l==r){tr[k].siz++; return k;}
	int mid=(l+r)>>1;
	if(pos<=mid){
		if(!tr[k].lc) tr[k].lc=++tottt;
		update(tr[k].lc,pos,l,mid);
	}else{
		if(!tr[k].rc) tr[k].rc=++tottt;
		update(tr[k].rc,pos,mid+1,r);
	}
	pushup(k); return k;
}
int merge(int x, int y){
	if(!x||!y) return x+y;
	u+=(long long)tr[tr[x].rc].siz*tr[tr[y].lc].siz;
	v+=(long long)tr[tr[x].lc].siz*tr[tr[y].rc].siz;
	tr[x].siz+=tr[y].siz;
	tr[x].lc=merge(tr[x].lc,tr[y].lc);
	tr[x].rc=merge(tr[x].rc,tr[y].rc);
	return x;
}
int n, point, cnt=0;
int Dfs(){
	++cnt; root[cnt]=++tottt;
	int now, pos; cin>>now;
	if(now==0){
		int lc, rc;
		lc=Dfs(); rc=Dfs();
		u=0, v=0;
		root[cnt]=merge(lc,rc);
		ans+=min(u,v);
	}else{
		update(root[cnt],now,1,n);
	}
	return root[cnt];
}
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n; Dfs(); cout<<ans<<'\n';
	return 0;
}