$PS:$这个树状数组跟楼上不一样

好不容易学会了树状数组逆序对……不过因为离散化写炸了调试了半天……

事实上，你会发现这篇题解跟之前好多$DALAO$的树状数组求逆序对并不一样……个人感觉这种方法更接近于树状数组的“数位整合”的思想$qwq$

首先对于逆序对，我们可以如此思考这个问题：对于每个数的逆序对，在一个数列中的数量都是一定的。那么我们可以对于数列$a$的每一个$a_i$,可以与$a_1$~$a_{i-1}$匹配出$k_i$个逆序对，那么

$ans$=$\Sigma_{1}^{n}k_i$。

以上应该不难理解……因为每多读入一个数，就会多和之前的数据新的逆序对……用数学公式表示只是为了向大佬靠拢啊$QWQ$.

那么其实，我们用树状数组记录在第$i$个数之前按有几个数比它小或等于他，即$a_i$ $<=$ $a_j$且$i<=j$那么我们就要删除这些数。即用$i-sum(value[i])$即可。

诶，这个地方类似桶桶桶的思想，用$0$或者$1$记录比$a[i]$小的数在$a[i]$有没有输入即可。

啊，之后因为树状数组的局限性太大了，所以这个地方要离散化一下$qwq$。

离散化……当然就是排个序，然后再重新覆盖回去啦$qwq$。

诶，好像这个题的时间瓶颈从找逆序对变成了$sort$？？？

但反正都是$O(nlogn)$/滑稽。

$emmmm$贴代码

struct tree{
    int num,tre;
}t[50001];
int answer[50001],now[50001],change[50001];
int n,ans=0;
inline int lowbit(int i) {
    return i&(-i);
}
inline void insert(int i,int x)
{
    while(i<=n)answer[i]+=x,i+=lowbit(i);
}
inline bool cmp(tree a,tree b){
    return a.tre<b.tre; 
}
inline int sum(int num){
    int res=0;
    for(;num;num-=lowbit(num))
    res+=answer[num];
    return res;
}
int main()
{
    memset(t,0,sizeof(t));
    cin>>n;
    for(int i=1;i<=n;i++){ 
        cin>>t[i].tre;
        t[i].num=i;
    } 
    sort(t+1,t+n+1,cmp);
    for(int i=1;i<=n;i++){
        change[t[i].num]=i;
    }
    //上面两个for都用来输入+离散化
    for(int i=1;i<=n;i++){
        insert(change[i],1);
        ans+=i-sum(change[i]);
    }
    //for(int i=1;i<=n;i++)cout<<answer[i]<<endl;
    cout<<ans;
}