给一棵$n(1≤n≤200000)$个叶子的二叉树，可以交换每个点的左右子树，要求前序遍历叶子的逆序对最少。

输入很恶心。就不多说了。

对于一个结点子树中比他大的结点产生影响，这一步可以用线段树合并。

如何选择交换左右子树。考虑在合并的时候若不交换，则贡献为右子树的$[l,mid]$的数量$\times$,左子树$[mid+1,r]$。交换则反之，这一步可以在合并的过程中实现。

代码

```c++

include

using namespace std;
typedef long long ll;

define pii pair

define ls tree[pos].l

define rs tree[pos].r

define mk make_pair

const int N = 1e6 + 10;
const int mod = 1e9 + 7;

int scnt, rt[N];

ll ans1, ans2;
ll ans;
struct seg
{
int l, r, sum;
} tree[N 20];
void pushup(int pos)
{
tree[pos].sum = tree[ls].sum + tree[rs].sum;
}
void modify(int &pos, int l, int r, int v)
{
if (!pos)
pos = ++scnt;
if (l == r)
{
tree[pos].sum++;
return;
}
int mid = (l + r) >> 1;
if (v <= mid)
modify(ls, l, mid, v);
else
modify(rs, mid + 1, r, v);
pushup(pos);
}
int merge(int u, int v, int l, int r)
{
if (!u || !v)
return u + v;
int pos = ++scnt;
if (l == r)
{
tree[pos].sum = tree[u].sum + tree[v].sum;
return pos;
}
int mid = (l + r) >> 1;
ans1 += 1ll tree[tree[u].l].sum tree[tree[v].r].sum;
ans2 += 1ll tree[tree[u].r].sum * tree[tree[v].l].sum;
ls = merge(tree[u].l, tree[v].l, l, mid);
rs = merge(tree[u].r, tree[v].r, mid + 1, r);
pushup(pos);
return pos;
}
int n;

void dfs(int &x)
{
int tmp, l, r;
x = 0;
scanf(“%d”, &tmp);
if (!tmp)
{
dfs(l), dfs(r);
ans1 = ans2 = 0;
//cout << tmp << endl;
x = merge(l, r, 1, n);
ans += min(ans1, ans2);
}
else
modify(x, 1, n, tmp);
}

int main()
{
scanf(“%d”, &n);
int tmp = 0;
dfs(tmp);
printf(“%lld\n”, ans);
}