我的第一篇题解

题目描述

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。比如一个序列为4 5 1 3 2，那么这个序列的逆序数为7，逆序对分别为(4, 1), (4, 3), (4, 2), (5, 1), (5, 3), (5, 2),(3, 2)。

思路

求逆序数对，即统计序列中每个元素的左边大于该元素的个数。

ans+=getsum(n)-getsum(a[i]);

因为会出现数据大于n的情况，所以想到离散化。

算法

树状数组、离散化、归并排序等。

离散化

离散化：把任何不在合适区间的数转化为不超过元素个数的数。 例如：{2022,8,29}->{3,1,2}

temp[i].val记录原数

temp[i].pos记录原数的位置

struct node{
	int val,pos;
}temp[maxn];

a[]为离散化好的数组

	sort(temp,temp+n,cmp);
	for(int i=0;i<n;i++)
	{
		if(i!=0&&temp[i].val==temp[i-1].val)
			a[temp[i].pos]=a[temp[i-1].pos];
		else
			a[temp[i].pos]=i+1;
	}

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lowbit(x) ((x)&(-x))

const int maxn=100005;
int n;
int a[maxn],c[maxn];
struct node{
	int val,pos;
}temp[maxn];
bool cmp(node a,node b)
{
	return a.val<b.val;
}
void update(int x)
{
	for(int i=x;i<=n;i+=lowbit(i))
		c[i]++;
}
ll getsum(int x)
{
	ll sum=0;
	for(int i=x;i>0;i-=lowbit(i))
		sum+=c[i];
	return sum;
}
int main()
{
	cin>>n;
	ll ans=0;
	for(int i=0;i<n;i++)
	{
		cin>>temp[i].val;
		temp[i].pos=i;	
	}
	sort(temp,temp+n,cmp);
	for(int i=0;i<n;i++)
	{
		if(i!=0&&temp[i].val==temp[i-1].val)
			a[temp[i].pos]=a[temp[i-1].pos];
		else
			a[temp[i].pos]=i+1;
	}
	for(int i=0;i<n;i++)
	{
		update(a[i]);
		ans+=getsum(n)-getsum(a[i]);
	}
	cout<<ans<<endl;
	return 0;
}