文件详细信息

下载本文件

本文件的大小为 1264 字节。

#include<cstdio>
template<typename T>
void read(T&num){
	int ch=getchar();
	num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
template<typename T>
void write(T a){
	static int ch[20],cnt=0;
	if(a<0)putchar('-'),a=-a;
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|48,a/=10;
	while(cnt)putchar(ch[--cnt]);
}
typedef long long ll;
const int maxn=200000;
int n,root;
ll ans,ans1,ans2;
struct Seg{
	int l,r,cnt;
}T[maxn*20];
void pushup(const int u){
	T[u].cnt=T[T[u].l].cnt+T[T[u].r].cnt;
}
int tot;
int merge(const int u1,const int u2){
	if(!u1||!u2)return u1|u2;
	T[u1].cnt+=T[u2].cnt;
	ans1+=(ll)T[T[u1].r].cnt*T[T[u2].l].cnt;
	ans2+=(ll)T[T[u1].l].cnt*T[T[u2].r].cnt;
	T[u1].l=merge(T[u1].l,T[u2].l);
	T[u1].r=merge(T[u1].r,T[u2].r);
	return u1;
}
void insert(int&u,const int l,const int r,const int k){
	if(!u)u=++tot;
	if(l==r){
		T[u].cnt++;
		return;
	}
	const int mid=(l+r)>>1;
	if(k<=mid)insert(T[u].l,l,mid,k);
	else insert(T[u].r,mid+1,r,k);
	pushup(u);
}
void dfs(int&u){
	int x,lc,rc;
	read(x);
	u=0;
	if(x==0){
		dfs(lc);
		dfs(rc);
		ans1=ans2=0;
		u=merge(lc,rc);
		ans+=ans1<ans2?ans1:ans2;
	}else insert(u,1,n,x);
}
int main(){
	read(n);
	dfs(root);
	write(ans),putchar('\n');
	return 0;
}