# 逆序数

``````4
2 4 3 1
``````

``4``

``````#include<stdio.h>
int sum=0;
void f1(int a[],int low,int mid,int high,int b[])
{
int i=low,j=mid+1;
int m=mid,n=high;
int k=0;
while (i<=m&&j<=n)
{
if (a[i]<=a[j])
b[k++]=a[i++];
else
{
b[k++]=a[j++];
sum+=mid-i+1;
}
}
while(i<=m)
b[k++]=a[i++];
while (j<=n)
b[k++]=a[j++];
for (i=0;i<k;i++)
a[low+i]=b[i];
}
void f(int a[],int low,int high,int b[])
{
int mid;
if(low<high)
{
mid=low+(high-low)/2;
f(a,low,mid,b);
f(a,mid+1,high,b);
f1(a,low,mid,high,b);
}
}
int main()
{
int n,i;
int a[50001];
int b[50001];
memset(b,0,sizeof(b));
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
f(a,0,n-1,b);
printf("%d\n",sum);
}
``````

``````#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 500005;

struct Node
{
int val;
int pos;
};

Node node[N];
int c[N], reflect[N], n;

bool cmp(const Node& a, const Node& b)
{
return a.val < b.val;
}

int lowbit(int x)
{
return x & (-x);
}

void update(int x)
{
while (x <= n)
{
c[x] += 1;
x += lowbit(x);
}
}

int getsum(int x)
{
int sum = 0;
while (x > 0)
{
sum += c[x];
x -= lowbit(x);
}
return sum;
}

int main()
{
while (scanf("%d", &n) != EOF && n)
{
for (int i = 1; i <= n; ++i)
{
scanf("%d", &node[i].val);
node[i].pos = i;
}
sort(node + 1, node + n + 1, cmp);   //排序
for (int i = 1; i <= n; ++i) reflect[node[i].pos] = i;   //离散化
for (int i = 1; i <= n; ++i) c[i] = 0;   //初始化树状数组
long long ans = 0;
for (int i = 1; i <= n; ++i)
{
update(reflect[i]);
ans += i - getsum(reflect[i]);
}
printf("%lld\n", ans);
}
return 0;
}
``````