求逆序对的两种方法

归并排序

归排求逆序对用到了二分的思想
设当前归并排序讲合并的区间为$[l,r]$[l,r]
由于归排二分，所以$[l,mid]$[l,mid]和$[mid+1,r]$[mid+1,r]两段区间都分别已经排好了序
在排序过程中，如果$a[i]>a[j]$a[i]>a[j]，那么$a[i+1]$a[i+1]到$a[mid]$a[mid]都会大于$a[j]$a[j]
即会产生$mid-i+1$mid−i+1个逆序对

---

code

O3 inline void msort(ll l,ll r)
{
	if (l==r)return;
	ll mid=(l+r)>>1,i=l,j=mid+1,k=l;
	msort(l,mid),msort(mid+1,r);
	while (i<=mid && j<=r)
	{
		if (a[i]<=a[j])b[k++]=a[i++];
		else b[k++]=a[j++],ans+=mid-i+1;
	}
	while (i<=mid)b[k++]=a[i++];
	while (j<=r)b[k++]=a[j++];
	fo(i,l,r)a[i]=b[i];
}

归排常数小，经常可以代替手打快排

---

树状数组