2327: 信息学奥赛一本通T1311-求逆序对(树状数组+离散化)

通过题目知道逆序对知道当前数后面比他小的数就是逆序对，那么我们知道树状数组返回的就是前缀和，那么我们只将数据当成下标从后往前放入树状数组中，然后对其+1，然后求他前面一个数的前缀和就是当前数的逆序对数

拿样例来说

3 2 3 2

    1 2 3 //下标

1  0 1 0   //输入2 前一个数为1，1的前缀和为0所以没有逆序数对

2  0 1 1   //输入3前一个数为2，2的前缀和为1所以逆序对数量为1

3  0 2 1   //输入2 前一个数为1，1的前缀和为0所以没有逆序数对

4  0 2 2   //输入3前一个数为2，2的前缀和为2所以逆序对数量为2

和为3

但是，因为我们用序列的数当下标，要定义的数组很大，或许会运行错误，所以我们要对其进行离散化

将

3 2 3 2标上下标变成

1 2 3 4然后对3 2 3 2进行从大到小排序（当数相同时下标大的在前面）下标变成3 1 4 2，我们从前往后输入

    3 1 4 2

1  0 0 1 0 //输入3，无逆序对

2  1 0 1 0 //输入1，无逆序对

3  1 0 1 1//输入4，逆序对个数为2；

4  1 1 1 1//输入2，逆序对为1；

和为3；

AC代码：

#include<bits/stdc++.h>
using namespace std;
struct f
{
	int x;
	int t;
}num[500005];
int arr[500005];
int n;
bool cmp(f a,f b)
{
	return a.x==b.x?a.t>b.t:a.x>b.x;
}
int lowbit(int x)
{
	return x&(-x);
}
int qurey(int x)
{
	int num=0;
	while(x)
	{
		num+=arr[x];
		x-=lowbit(x);
	}
	return num;
}
void add(int x)
{
	while(x<=n)
	{
		arr[x]++;
		x+=lowbit(x);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&num[i].x);
		num[i].t=i;
	}
	sort(num+1,num+n+1,cmp);
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		add(num[i].t);
		ans+=qurey(num[i].t-1);
	}
	printf("%lld",ans);
	return 0;
}