树状数组求逆序对

## $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$贴代码 ```cpp 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; } ```