树状数组求逆序对
皎月半洒花
·
·
题解
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)/滑稽。
```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;
}
```