P3521 [POI2011] ROT-Tree Rotations

样例已过，只有2分

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
int n,cnt,r[N*20],ls[N*20],rs[N*20],t[N*20];
long long ans,a,b;

void update(int &u,int l,int r,int g){
	if(!u) u=++cnt;
	if(l==r){t[cnt]=1;return ;}
	int mid=(l+r)>>1;
	if(g<=mid) update(ls[u],l,mid,g);
	else update(rs[u],mid+1,r,g);
	t[u]=t[ls[u]]+t[rs[u]];
}

int Merge(int a,int b,int l,int r,long long &A1,long long &A2){
	if(!a||!b) return a+b;
	if(l==r){t[a]+=t[b];return a;}
	int mid=(l+r)>>1;
	ls[a]=Merge(ls[a],ls[b],l,mid,A1,A2);
	rs[a]=Merge(rs[a],rs[b],mid+1,r,A1,A2);
	A1+=t[ls[a]]*t[rs[b]],A2+=t[ls[b]]*t[rs[a]];
	t[a]=t[ls[a]]+t[rs[a]];
	return a;
}

int dfs(){
	int u=0,x;
	scanf("%d",&x);
	if(x) update(u,1,n,x);
	else{
		int lk=dfs(),rk=dfs();
		long long a1=0,a2=0;
		u=Merge(lk,rk,1,n,a1,a2);
		ans+=min(a1,a2);
	}
	return u;
}

int main(){
	scanf("%d",&n);
	dfs();
	printf("%lld",ans);
	return 0;
}