//Bismillahir-Rahmanir-Rahim
# include <bits/stdc++.h>
# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define all(x) (x).begin(), (x).end()
# define deb(x) cerr << #x << " = " << x << endl;
# define pll pair <ll, ll>
# define pii pair <int, int>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll maxn = 1e6 + 2;
const ll inf = 2e18 + 0;
const ll mod = 1e9 + 7;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};
using namespace std;
int n, nv;
int L[maxn];
int R[maxn];
int sz[maxn];
int cnt[maxn];
ште t[maxn];
ll dp[maxn];
void upd (int id, int x)
{
for (; id <= n; id += (id & (-id)))
{
t[id] += x;
}
}
int get (int id)
{
int res = 0;
for (; id >= 1; id -= (id & (-id)))
{
res += t[id];
}
return res;
}
void calc (int v = n + 1)
{
if (v <= n)
{
sz[v] = 1, cnt[v] = 1;
return;
}
calc(L[v]); calc(R[v]);
sz[v] = sz[L[v]] + sz[R[v]] + 1;
cnt[v] = cnt[L[v]] + cnt[R[v]];
}
void updv (int v, int x)
{
if (v <= n)
{
upd(v, x);
return;
}
updv(L[v], x);
updv(R[v], x);
}
ll count (int v)
{
if (v <= n) return get(v);
return count(L[v]) + count(R[v]);
}
void dfs (int v = n + 1, bool keep = 1)
{
if (v <= n)
{
if (keep)
{
updv(v, 1);
}
return;
}
if (sz[L[v]] < sz[R[v]])
{
swap(L[v], R[v]);
}
dfs(R[v], 0); dfs(L[v], 1);
ll inv = count(R[v]);
dp[v] = dp[L[v]] + dp[R[v]] + min(inv, cnt[L[v]] * cnt[R[v]] - inv);
if (keep)
{
updv(R[v], 1);
}
else
{
updv(L[v], -1);
}
}
int rec ()
{
int x; cin >> x;
if (!x)
{
int v = ++nv;
L[v] = rec ();
R[v] = rec ();
return v;
}
return x;
}
void ma1n (/* SABR */)
{
cin >> n;
nv = n;
rec ();
calc ();
dfs ();
cout << dp[n + 1];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
int ttt = 1;
// cin >> ttt;
for (int test = 1; test <= ttt; ++test)
{
// cout << "Case " << test << ":" << '\n';
ma1n();
}
return 0;
}
// 998batrr | BbIWEJI 3A TObOU!!!
// tourist | BbIWEJI 3A TObOU!!!
Compilation message
rot.cpp:32:1: error: '\U00000448\U00000442\U00000435' does not name a type
32 | ште t[maxn];
| ^~~
rot.cpp: In function 'void upd(int, int)':
rot.cpp:39:9: error: 't' was not declared in this scope
39 | t[id] += x;
| ^
rot.cpp: In function 'int get(int)':
rot.cpp:48:16: error: 't' was not declared in this scope
48 | res += t[id];
| ^
