树状数组求逆序数的模板(离散化处理)

最近刚接触线段树，今天刚弄懂树状数组；听说用树状数组解决逆序数很高效；所以也就整理了一下，随带整理了一下离散化；

把这个模板贴上，以后碰到逆序数的题目，就可以直接用了；

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
#include<cmath>
#include<stack>
#include<set>
#include<vector>
#include<algorithm>
#define LL long long
#define inf 1<<30
#define s(a) scanf("%d",&a)
#define Clear(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=200005;
int n;
int a[N],aa[N],b[N],bb[N];
int c[N];
int lowbit(int x)       //  返回出右边出现第一个1的值；
{
    return x&(-x);
}
void add(int i,int v)   //  添加数据；
{
    while(i<=n){
        c[i]+=v;
        i+=lowbit(i);
    }
}
int sum(int i)  //  求区间和；
{
    int ans=0;
    while(i){
        ans+=c[i];
        i-=lowbit(i);
    }
    return ans;
}
int Unique(int b[])     //  去重，保存在数组bb，并且返回去重后的长度；
{
    int t=1,m=1;    //  bb小标重1开始；
    bb[1]=b[0];
    while(t<=n){
        if(b[t]!=b[t-1]) bb[++m]=b[t++];
        else t++;
    }
    return m;
}
int main()
{
    //freopen("../../in.txt","r",stdin);
    //freopen("../../out.txt","w",stdout);
    while(~scanf("%d",&n)){
        Clear(c,0);
        for(int i=0;i<n;i++){
            s(a[i]);
            b[i]=a[i];
        }
        sort(b,b+n);        //  排序；
        int len=Unique(b);  //  去重；
        int cnt=0;
        for(int i=0;i<n;i++){
            int pos=lower_bound(bb+1,bb+len,a[i])-bb; //  返回第一个小于等于的下标；
            aa[i]=pos;          //  离散成对应值的下标；
            cnt+=i-sum(pos);  //  计算总和；
            add(pos,1);     //  插入；
        }/* HDU1394;
        int ans=cnt;        //  算将第一个数放到末尾所形成的最小逆序数；
        for(int i=0;i<n;i++) cnt=cnt-2*(aa[i]-1)+n-1,ans=min(ans,cnt);
        */printf("%d\n",cnt);
    }
    return 0;
}