自动搬运

查看原文

来自洛谷，原作者为

	IC_QQQ **

搬运于2025-08-24 21:49:47，当前版本为作者最后更新于2019-05-13 20:57:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

正如前面大佬们所说的： 权值线段树和线段树合并。

对于任意一个节点，交换左右子树对当前节点和前面的所有节点没有影响。

因为这是前序遍历：根节点->左子树->右子树。可以看到，交换左右子树对前面的节点无影响。

我们要求的是逆序对最小，对于一个节点，逆序对有三种：

• 在左子树中。
• 在右子树中。
• 跨越了左右子树。

我们清楚，交换子树只会对第三种情况产生影响。因此，我们只需要在合并线段树的过程中统计交换子树的逆序对个数u和不交换子树的逆序对个数v，取 min(u,v) 累加到答案中就行了。

现在的问题是如何找第三种情况下的逆序对。

上图：

用p表示左子树，q表示右子树。ls表示左子节点，rs表示右子节点。

很明显，对于除了叶节点的每一个节点：

1. 如果不交换： $u+=[p.rs].size*[q.ls].size$ 。
2. 如果交换： $v+=[p.ls].size*[q.rs].size$。

重点：每一次合并线段树时，递归到除了叶节点的所有节点，都要累加逆序对个数u,v。

看图模拟一边很容易就明白了。

比如，递归到[1~4]这个节点时，累加u:我们只累加了3、4对1、2行成的 $2*2=4$ 组逆序对。但是继续向下递归到[3~4]时，4对3还有一组逆序对。

因此，递归到除了叶节点的所有节点时，都要进行累加 u,v 的操作。

讲完了。

补充------空间复杂度：

我们对每个叶节点都需要进行建树操作，该建树操作的值域是 $[1,n]$ ，而我们每次建树都得到一条链，这条链的长度就是 $logn$ ，因为有 $logn$ 层。 考虑极限情况，有大约 n 个叶节点，那么总的空间就是 $nlogn$ 。

注意： 线段树合并不需要新开节点。

通俗易懂的代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
int n,top;//top：创建节点个数 
ll ans,u,v;//u,v：逆序对个数 
struct Tree{
	int ls,rs,size;
}da[22*N];//N*logN的空间 

int in(){//快读 
	int x=0;char ch=getchar();
	while(ch>'9'||ch<'0') ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
}

int update(int l,int r,int val){//创建权值线段树 
	int pos=++top;
	da[pos].size++;
	if(l==r) return pos;
	int mid=(l+r)>>1;
	if(val<=mid) da[pos].ls=update(l,mid,val);
	else da[pos].rs=update(mid+1,r,val);
	return pos;
}

int merge(int p,int q,int l,int r){//合并线段树 
	if(!q||!p) return (!p)?q:p;//如果有节点为空，返回另一个节点 
	if(l==r){ da[p].size+=da[q].size; return p; }//叶节点，合并，返回 
	u+=(ll)da[da[p].rs].size*da[da[q].ls].size;//交换前 
	v+=(ll)da[da[p].ls].size*da[da[q].rs].size;//交换后 
	int mid=(l+r)>>1;
	da[p].ls=merge(da[p].ls,da[q].ls,l,mid);//继续合并左子节点 
	da[p].rs=merge(da[p].rs,da[q].rs,mid+1,r);//右子节点 
	da[p].size=da[da[p].ls].size+da[da[p].rs].size;//重置更新当前节点 
	return p;
} 

int dfs(){
	int pos,val=in();
	if(val==0){//不是叶节点 
		int ls=dfs(),rs=dfs();//ls:左子树的权值线段树的根节点，rs同理 
		u=0;v=0;//记得每次清零 
		pos=merge(ls,rs,1,n);//pos：合并后的权值线段树的根节点 
		ans+=min(u,v);//累加答案 
	}
	else pos=update(1,n,val);//叶节点，建树 
	return pos;//返回这颗权值线段树的根节点 
}

int main(){
	n=in();
	dfs();
	printf("%lld",ans);
	return 0;
}