双倍经验题……
首先两个子树内怎么排列对两个子树之间产生的逆序对没有影响，所以对于每个节点都要选择交换或者不交换，使得这两个子树形成的逆序对数最小，全局逆序对数就最小了
每个点维护一个权值线段树，里边是子树里的权值，非叶子节点的等于两个儿子节点的线段树合并，而我们在合并的过程中就可以算出来逆序对数
复杂度O(n log n)
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<iomanip> #include<cstring> #include<cmath> #include<ctime> #include<vector> #include<stack> #include<queue> #include<set> #include<bitset> #include<map> using namespace std; #define MAXN 800010 #define MAXM 6000010 #define INF 1000000000 #define MOD 1000000007 #define ll long long #define eps 1e-8 int n; int l[MAXN],r[MAXN]; int RT,TOT; int v[MAXN]; int rt[MAXN]; int siz[MAXM],son[MAXM][2]; int tot; ll ans; void change(int &x,int l,int r,int p){ if(!x){ x=++tot; } siz[x]++; if(l==r){ return ; } int mid=l+r>>1; if(p<=mid){ change(son[x][0],l,mid,p); }else{ change(son[x][1],mid+1,r,p); } } ll ad1,ad2; int merge(int x,int y){ if(!x||!y){ return x+y; } ad1+=(ll)siz[son[x][0]]*siz[son[y][1]]; ad2+=(ll)siz[son[x][1]]*siz[son[y][0]]; son[x][0]=merge(son[x][0],son[y][0]); son[x][1]=merge(son[x][1],son[y][1]); siz[x]+=siz[y]; return x; } void get(int &x){ x=++TOT; scanf("%d",&v[x]); if(!v[x]){ get(l[x]); get(r[x]); ad1=ad2=0; rt[x]=merge(rt[l[x]],rt[r[x]]); ans+=min(ad1,ad2); }else{ change(rt[x],1,n,v[x]); } } int main(){ scanf("%d",&n); get(RT); printf("%lld\n",ans); return 0; } /* 4 0 0 1 3 0 4 2 */
