#include <bits/stdc++.h>
mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define int long long
using namespace std;
const int N=4e5+5;
int bit[N],sz[N],value[N],id=1,l,r,n,ans[N];
vector<int>g[N];
void input(){
int x;
cin>>x;
value[id]=x;
if (x) return;
int k=id;
g[k].push_back(++id);
input();
g[k].push_back(++id);
input();
}
int getSum(int p) {
int idx = p, res = 0;
while (idx > 0) {
res += bit[idx];
idx -= (idx & (-idx));
}
return res;
}
void update(int u, int v) {
int idx = u;
while (idx <= N) {
bit[idx] += v;
idx += (idx & (-idx));
}
}
void cnt(int id){
if(value[id]){
sz[id]=1;
return;
}for(int x:g[id]){
cnt(x);
sz[id]+=sz[x];
}return;
}
void add(int id, int val){
if(value[id]){
update(value[id],val);
return;
}for(int x:g[id]) add(x,val);
}
void cal(int id){
if(value[id]){
l+=getSum(value[id]);
r+=getSum(n)-getSum(value[id]);
return;
}for(int x:g[id]) cal(x);
}
void solve(int id){
if(value[id]){
update(value[id],1);
return;
}int x=g[id][0];
int y=g[id][1];
solve(x);solve(y);
ans[id]=ans[x]+ans[y];
if(sz[x]>sz[y]) swap(x,y);
add(x,-1);
l=0;r=0;
cal(x);
add(x,1);
ans[id]+=min(l,r);
return;
}
signed main() {
cin>>n;
input();
cnt(1);
solve(1);
cout<<ans[1];
return 0;
}
Compilation message
rot.cpp:2:1: error: 'mt19937_64' does not name a type
2 | mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
| ^~~~~~~~~~
