- 考虑一个子树 (x) 的左右儿子分别为 (ls,rs) .那么子树 (x) 内的逆序对数就是 (ls) 内的逆序对数,(rs) 内的逆序对数,跨越 (ls,rs) 的逆序对数三者之和.
- 交换 (ls,rs) 显然对前两种的答案没有影响,只需最大化最后一种答案.
- 对每个叶子节点开一棵权值线段树向上合并,选取权值中点 (mid) 划分开,那么两种情况在当前层产生的贡献即为 (ls) 的左子树大小 ( imes) (rs) 的右子树大小,(ls) 的右子树大小 ( imes) (rs) 的左子树大小中的最大值.
- 继续递归合并,就可以计算到所有贡献.
- 时间复杂度为 (O(nlogn)) .
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
int out=0,fh=1;
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
fh=-1,jp=getchar();
while (jp>='0'&&jp<='9')
out=out*10+jp-'0',jp=getchar();
return out*fh;
}
const int MAXN=2e5+10;
ll ans=0,ans1,ans2;
struct node{
int siz,ls,rs;
}Tree[MAXN*30];
#define root Tree[o]
#define lson Tree[root.ls]
#define rson Tree[root.rs]
#define t(x) Tree[x]
int n,cnt=0;
void update(int &o,int l,int r,int pos)
{
if(!o)
o=++cnt;
++root.siz;
if(l==r)
return;
int mid=(l+r)>>1;
if(pos<=mid)
update(root.ls,l,mid,pos);
else
update(root.rs,mid+1,r,pos);
}
int merge(int ls,int rs)
{
if(!ls || !rs)
return ls+rs;
t(ls).siz+=t(rs).siz;
ans1+=1LL*(Tree[t(ls).ls].siz)*(Tree[t(rs).rs].siz);
ans2+=1LL*(Tree[t(ls).rs].siz)*(Tree[t(rs).ls].siz);
t(ls).ls=merge(t(ls).ls,t(rs).ls);
t(ls).rs=merge(t(ls).rs,t(rs).rs);
return ls;
}
int solve()
{
int p=read(),x=0;
if(!p)
{
int ls=solve();
int rs=solve();
ans1=ans2=0;
x=merge(ls,rs);
ans+=min(ans1,ans2);
return x;
}
else
update(x,1,n,p);
return x;
}
int main()
{
n=read();
solve();
cout<<ans<<endl;
return 0;
}