题目描述
给定一个长度为 $n$ 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 $i$ 个和第 $j$ 个元素，如果满足 $i < j$ 且 $a\[i\] > a\[j\]$，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 $n$，表示数列的长度。
第二行包含 $n$ 个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
$1 \\le n \\le 100000$，
数列中的元素的取值范围 $\[1,10^9\]$。
输入样例：
6
2 3 4 5 6 1
输出样例：
5
方法一:归并排序
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAXN 100010
using namespace std;
typedef long long ll;
int n,a[MAXN],temp[MAXN];
ll res=0;
void merge_sort(int q[],int l,int r)
{
if(l>=r)
return ;
int mid=(l+r)/2;
merge_sort(q,l,mid);
merge_sort(q,mid+1,r);
int k=1,i=l,j=mid+1;
while(i<=mid&&j<=r)
{
if(q[i]<=q[j])
temp[k++]=q[i++];
else
{
res+=(mid-i+1);//增添部分
temp[k++]=q[j++];
}
}
while(i<=mid)
temp[k++]=q[i++];
while(j<=r)
temp[k++]=q[j++];
for(int i=l,j=1;i<=r;i++,j++)
q[i]=temp[j];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
merge_sort(a,1,n);
printf("%lld\n",res);
return 0;
}
方法二.1:树状数组(正序处理)+离散化
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAXN 200010
using namespace std;
typedef long long ll;
int n;
struct node{
int num;
int pos;
}s[MAXN];
int id[MAXN],C[MAXN];
ll res;
int cmp(node a,node b)
{
if(a.num==b.num)
return a.pos<b.pos;
return a.num<b.num;
}
int lowbit(int x)
{
return x&-x;
}
void add(int x,int val)
{
for(int i=x;i<=n;i+=lowbit(i))
C[i]+=val;
}
ll sum(int x)
{
ll ans=0;
for(int i=x;i>=1;i-=lowbit(i))
ans+=C[i];
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&s[i].num);
s[i].pos=i;
}
sort(s+1,s+n+1,cmp);
for(int i=1;i<=n;i++)
id[s[i].pos]=i;
for(int i=1;i<=n;i++)
{
add(id[i],1);
res+=i-sum(id[i]);
}
printf("%lld\n",res);
return 0;
}
方法二.2:树状数组(逆序处理)+离散化
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAXN 100010
using namespace std;
typedef long long ll;
int n;
struct node{
int num;
int pos;
}s[MAXN];
int id[MAXN],C[MAXN];
ll res;
int cmp(node a,node b)
{
if(a.num==b.num)
return a.pos<b.pos;
return a.num<b.num;
}
int lowbit(int x)
{
return x&-x;
}
void add(int x,int val)
{
for(int i=x;i<=n;i+=lowbit(i))
C[i]+=val;
}
ll sum(int x)
{
ll ans=0;
for(int i=x;i>=1;i-=lowbit(i))
ans+=C[i];
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&s[i].num);
s[i].pos=i;
}
sort(s+1,s+n+1,cmp);
for(int i=1;i<=n;i++)
id[s[i].pos]=i;
for(int i=n;i>=1;i--)
{
add(id[i],1);
res+=sum(id[i]-1);
}
printf("%lld\n",res);
return 0;
}
方法三:线段树+离散化
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAXN 100010
using namespace std;
typedef long long ll;
int n;
struct node{
int num;
int pos;
}s[MAXN];
int id[MAXN];
ll res;
int cmp(node a,node b)
{
if(a.num==b.num)
return a.pos<b.pos;
return a.num<b.num;
}
struct Tree{
int l;
int r;
int dat;
}tree[4*MAXN];
void pushup(int root)
{
tree[root].dat=tree[2*root].dat+tree[2*root+1].dat;
}
void build(int root,int l,int r)
{
tree[root].l=l,tree[root].r=r;
if(l==r)
{
tree[root].dat=0;
return ;
}
int mid=(l+r)/2;
build(2*root,l,mid);
build(2*root+1,mid+1,r);
pushup(root);
}
void modify(int root,int pos,int val)
{
if(tree[root].l==pos&&tree[root].r==pos)
{
tree[root].dat+=val;
return ;
}
int mid=(tree[root].l+tree[root].r)/2;
if(pos<=mid)
modify(2*root,pos,val);
else modify(2*root+1,pos,val);
pushup(root);
}
ll query(int root,int l,int r)
{
if(l<=tree[root].l&&r>=tree[root].r)
return tree[root].dat;
int mid=(tree[root].l+tree[root].r)/2;
ll ans=0;
if(l<=mid)
ans+=query(2*root,l,r);
if(r>mid)
ans+=query(2*root+1,l,r);
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&s[i].num);
s[i].pos=i;
}
sort(s+1,s+n+1,cmp);
for(int i=1;i<=n;i++)
id[s[i].pos]=i;
build(1,1,n);
for(int i=n;i>=1;i--)
{
modify(1,id[i],1);
res+=query(1,1,id[i]-1);
}
printf("%lld\n",res);
return 0;
}
