在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

 

如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。给出一个整数序列，求该序列的逆序数。

Input第1行：N，N为序列的长度（n <= 50000) 

第2 - N + 1行：序列中的元素（0 <= Aii <= 10^9）Output输出逆序数Sample Input

42431

Sample Output

4

逆序数如上所述，就是一对数的前后位置与大小顺序相反，即前面的数大于后面的数，这个东西里离散还会讲的，

这道题需要先离散数据，要不TLE的

树状数组的代码如下

#include 
     
      #include 
      
       using namespace std;const int N = 500005;struct Node{    int val;    int pos;    friend bool operator <(Node a,Node b)    {        return a.val < b.val;    }};Node node[N];int c[N], hash[N], n;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(){    scanf("%d", &n);    for (int i = 1; i <= n; ++i)    {        scanf("%d", &node[i].val);        node[i].pos = i;    }    sort(node + 1, node + n + 1);    for (int i = 1; i <= n; ++i)         hash[node[i].pos] = i;    int  ans = 0;    for (int i = 1; i <= n; ++i)    {        update(hash[i]);        ans += i - getsum(hash[i]);    }    printf("%d\n", ans);    return 0;}
      
     

 

TLE的代码

#include 
     
      using namespace std;#define N 500005int c[N];int n;int lowbit(int i){    return i&(-i);}int insert(int i,int x){    while(i<=n)    {        c[i]+=x;        i+=lowbit(i);    }    return 0;}int getsum(int i){    int sum=0;    while(i>0)    {        sum+=c[i];        i-=lowbit(i);    }    return sum;}int main(){    while(cin>>n)    {        int ans=0;        memset(c,0,sizeof(c));        for(int i=1; i<=n; i++)        {            int a;            cin>>a;            insert(a,1);            ans+=i-getsum(a);        }        cout<
      
       <