RT
评测记录

#include <bits/stdc++.h>
using namespace std;
#define _ (int)(2e5 + 5) 
#define Mid int mid = (l + r) >> 1
#define ls cot << 1
#define rs cot << 1 | 1
int n;
int lc[_ * 22], rc[_ * 22];
int sum[_ * 22];
int root[_ * 4], cnt;
void pushup(int p)
{
    sum[p] = sum[lc[p]] + sum[rc[p]];
}
void update(int &p, int l, int r, int x)
{
    if (!p)
        p = ++cnt;
    if (l == r)
    {
        sum[p]++;
        return;
    }
    Mid;
    if (x <= mid)
        update(lc[p], l, mid, x);
    else
        update(rc[p], mid + 1, r, x);
    pushup(p);
}
long long u, v;

int merge(int a, int b, int l, int r)
{
    if(!a || !b)
        return a + b;
    if(l == r) {
        sum[a] = sum[a] + sum[b];
        return a;
    }
    Mid;
    u += (long long)sum[rc[a]] * sum[lc[b]];
    v += (long long)sum[lc[a]] * sum[rc[b]];
    lc[a] = merge(lc[a], lc[b], l , mid);
    rc[a] = merge(rc[a], rc[b], mid + 1, r);
    pushup(a);
    return a;
}
long long ans;
void dfs(int cot)
{
    int now;
    cin >> now;
    if (now)
        return update(root[cot], 1, n, now);
    else
    {
        dfs(ls);
        dfs(rs);
    }
    u = v = 0;
    root[ls] = merge(root[ls], root[rs], 1, n);
    ans += min(u, v);
    root[cot] = root[ls];
}
signed main()
{
    cin >> n;
    dfs(1);
    cout << ans;
    return 0;
}