波兰人太神秘了，竟能出出来如此题目。
题意
给一棵树（读入不太寻常，这个容易处理，忽略不计）, 每个叶子节点有一个权值，我们可以选择交换一些节点的左右子树（保证是二叉树，且要么是叶子要么左右子树都存在）。
经过交换后，跑前序遍历，求最小化的逆序对数量。
大小不好说，大概是 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;
}