hdu:sort it(逆序对，离散化)

Problem Description
给定n（n<=100000）个正整数，希望对其从小到大排序，如果采用冒泡排序算法，请计算需要进行的交换次数。

Input
输入包含多组测试用例，每组用例由两行组成：
第一行包含一个正整数n（n <=100000）;
第二行包含n个不同的正整数Ai（Ai<=109）。

Output
对于每组测试用例，请输出采用冒泡排序算法需要进行的交换次数。
每组数据输出一行。

输入样例

4
40000 200 3000 10
3
10 20000 300000000

输出样例

5
0

求逆序对的和，数据范围离散化后用树状数组
附ac代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct s{
    int val;
    int ord;
}a[N];
int c[N];
int lowbit(int i)
{
    return i&-i;
}
void update(int i,int n)
{
    while(i<=n)
    {
        c[i]++;
        i+=lowbit(i);
    }
}
int sum(int i)
{
    int ans=0;
    while(i>0)
    {
        ans+=c[i];
        i-=lowbit(i);
    }
    return ans;
}
bool cmp(s s1,s s2)
{
   return s1.val<s2.val;
}
bool cmp1(s s1,s s2)
{
    return s1.ord<s2.ord;
}
int main()
{
    int n;
    while(cin>>n)
    {
    memset(a,0,sizeof(a));
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i].val);
        a[i].ord=i;
    }
    sort(a+1,a+n+1,cmp);
    int cnt=1;
    a[1].val=cnt;
    for(int i=2;i<=n;++i)
    {
      if(a[i].val!=a[i-1].val)
        cnt++;
      a[i].val=cnt;
    }
    sort(a+1,a+n+1,cmp1);
    long long ans=0;
    for(int i=1;i<=n;++i)
    {
        update(a[i].val,cnt);
        ans+=sum(cnt)-sum(a[i].val);
        //用cnt不用n,a[i].val不是a[i].val-1
    }
    printf("%lld\n",ans);
    }
}