树状数组和归并算法求逆序对

引入

什么是逆序对？
概念：对于一对数字$ai, aj$ai,aj，当$i&lt;j$i<j且$ai&gt;aj$ai>aj时，称这一对数字为逆序对。

对于求逆序对而言，一般是有两种不同的解决方法，其一是树状数组，其二是归并排序。（我个人比较倾向于树状数组，毕竟是很早以前就学过了的算法，现在复习一遍印象深刻，但是归并就学的太早了，现在复习也是很模糊。。。）

树状数组求逆序对

对于一个序列$a$a而言，我们可以把$a$a数组的数值范围当做树状数组维护的值。

1. 倒序初始化插入$a$a序列的值，这样子的话就可以保证在插入$i$i的时候树状数组中就只有$i$i和他后面的数值，而没有他前面的。
2. 这样子的话，就在插入$ai$ai的时候查找一下在树状数组中$ai$ai之前是否有值，有几个值就是$ai$ai构成的逆序对数。

重点：

1. 数值范围作为树状数组维护的值；
2. 倒序插入。

参考例题：https://www.luogu.org/problemnew/show/P1908

code

//树状数组求逆序对 
#include <bits/stdc++.h>
using namespace std;

const int nn=5e5+5;
typedef long long ll;

int n;
int maxx=-1000;
int a[nn],b[nn];
ll c[nn];

inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
	return x*f;
}

void read_d()//离散化 
{
	n=read();
	for(int i=1;i<=n;++i)	a[i]=read(),b[i]=a[i];
	sort(b+1,b+1+n);
	int lb=unique(b+1,b+1+n)-(b+1);
	for(int i=1;i<=n;++i)
		a[i]=lower_bound(b+1,b+1+lb,a[i])-b;
}

void add(int x,int y)
{
	for( ;x<=n;x+=x&(-x))
		c[x]+=y;
}

ll ask(int x)
{
	ll sum=0;
	for( ;x>0;x-=x&(-x))
		sum+=c[x];
	return sum;
}

int main()
{
	read_d();/*离散化*/
	ll ans=0;
	for(int i=n;i>=1;--i)/*倒序处理*/
	{
		add(a[i],1);
		ans+=ask(a[i]-1);/*找到a[i]之前的数字，并不包括a[i]*/
	}
	printf("%lld\n",ans);/*注意最后结果要开longlong*/
	return 0;
}

---

归并排序