1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 200010
#define ll long long
using namespace std;
int n, m;
#define lc T[i].ch[0]
#define rc T[i].ch[1]
#define Lc T[j].ch[0]
#define Rc T[j].ch[1]
struct Seg {
int v, ch[2];
} T[maxn * 20]; int rt[maxn * 2], top;
inline void maintain(int i) { T[i].v = T[lc].v + T[rc].v; }
void update(int &i, int l, int r, int k, int v) {
if (!i) i = ++top;
if (l == r) return (void) (T[i].v += v);
int m = l + r >> 1;
if (k <= m) update(lc, l, m, k, v);
else update(rc, m + 1, r, k, v);
maintain(i);
}
ll s1, s2;
void merge(int &i, int j, int l, int r) {
if (!i) return (void) (i = j);
if (!j) return ;
if (l == r) return (void) (T[i].v += T[j].v);
int m = l + r >> 1;
s1 += 1ll * T[lc].v * T[Rc].v;
s2 += 1ll * T[Lc].v * T[rc].v;
merge(lc, Lc, l, m); merge(rc, Rc, m + 1, r);
maintain(i);
}
struct node {
int ls, rs;
} a[maxn * 2]; int Rt, cnt;
ll ans;
void dfs(int &u) {
int x; scanf("%d", &x); u = ++cnt;
if (x) return update(rt[u], 1, n, x, 1);
dfs(a[u].ls); dfs(a[u].rs); s1 = s2 = 0;
merge(rt[a[u].ls], rt[a[u].rs], 1, n); rt[u] = rt[a[u].ls];
ans += min(s1, s2);
}
int main() {
cin >> n; dfs(Rt);
cout << ans << endl;
return 0;
}
|