P1908 逆序对
码迷元首
·
·
个人记录
原题目
选择算法
可以选择归并排序，但是这里用树状数组。
## 具体分析
逆序对，简单来说就是两个数中较大的数放在较小的数的前面。
而线段树经常用来求带修改元素的部分和。
有没有一种可能，记下序列中每个数排第几，然后将序列进行从大到小排序。接着按照排序后的顺序，把树状数组arr的ord（每个数的输入时的序号）元素增加1，ans累加arr的元素1..ord-1；表示把排在当前元素前面，而又比当前元素大（由于已经按元素的从大到小的顺序插入）的元素个数累加起来。
注意：记得用稳定排序，对比的两个元素的值相同时还是按照原来的顺序。
## Source Code
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+1;
#define int long long
struct ele
{
int val,ord;
}a[N];
int n,tr[N],ans;
int lowbit(int a)
{
return a&(-a);
}
void add(int x,int k)
{
for(;x<=n;x+=lowbit(x))
tr[x]+=k;
}
int query(int x)
{
int sum=0;
for(;x>0;x-=lowbit(x))
sum+=tr[x];
return sum;
}
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i].val);
a[i].ord=i;
}
stable_sort(a+1,a+1+n,*[](ele a,ele b){
if(a.val==b.val)
return a.ord>b.ord;
return a.val>b.val;
});
for(int i=1;i<=n;i++)
{
add(a[i].ord,1);
ans+=query(a[i].ord-1);
}
printf("%lld",ans);
}
```