信息学奥赛一本通T1311-求逆序对-题解（C++代码）

解题思路:

给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目。

输入

第一行，一个数 n，表示序列中有 n个数。

第二行 n 个数，表示给定的序列。序列中每个数字不超过 int 所表示的范围。

输出

所有逆序对总数。

样例输入

4
3 2 3 2

样例输出

3

提示

数据经过加强！！！

对于 25% 的数据，n≤2500

对于 50% 的数据，n≤4×104。

对于所有数据，n≤5×105

请使用较快的输入输出

这里数据是经过加强的，求逆序对一般有两种做法，一种是线段树和树状数组，还有

一种是归并排序。这里建议使用树状数组。而不建议使用线段树。我在尝试使用归并

排序的时候时间超限了。。。

注意事项:

1.这里数据范围是整形，但数组开不了那么大，所以要使用离散化处理

2.题目要求要快速输入。

3.在数组范围大的时候，建议不要使用memset来初始化，建议嵌套在输入循环语句中初始化，

不然很容易时间超限。

参考代码:

//  求逆序对，树状数组
//  需要离散化 
#include <iostream>
#include <algorithm>
using namespace std;
int tree[500005];
int A[500005],B[500005];
int n;
int cnt = 1;
//快速输入代码 
int read() {
char ch = getchar();
int num = 0;
bool fl = 0;
for(; !isdigit(ch); ch = getchar())
if (ch=='-') fl = 1;
for(; isdigit(ch); ch = getchar())
num = (num<<1)+(num<<3)+ch-48;
if(fl) num = -num;
return num;
}
int lowbit(int k)
{
return k&(-k);
}
void updata(int k,int num)
{
  while(k<=cnt)
  {
  tree[k]+=num;
  k+=lowbit(k);
  }
} 
int getsum(int k)
{
int ans = 0;
while(k)
{
ans+=tree[k];
k-=lowbit(k);
}
return ans;
}
int getnum(int t,int ri)
{
int le = 1;
int mid=(le+ri)/2;
while(le<ri)
{
if(B[mid]==t) return (mid);
else if(B[mid]>t)
{
ri = mid-1;
mid=(le+ri)/2;
}
else
{
le=mid+1;
mid=(le+ri)/2;
}
}
}
int main()
{
cin>>n;
for(int i = 1;i<=n;i++)
{   
A[i] =read();
B[i] = A[i];
}
//离散化处理
sort(B+1,B+n+1);
tree[1] = 0;
for(int i =2;i<=n;i++)
{
if(B[i]!=B[i-1]) 
{
B[++cnt] = B[i];
tree[cnt] = 0;
}
}
int t;
long long sum = 0;
for(int i = 1;i<=n;i++)
{
int t =getnum(A[i],cnt);
//cout<<t<<endl;
updata(t,1);
sum = sum+(i-getsum(t));
}
printf("%lld",sum);
return 0;
 }