P1908 逆序对

经典的逆序对问题。

思路

将数字看作树状数组的下标，由于数字的值域可能会很大，因此要先进行离散化。

假如是正序，每次把对应数字下标的元素加一，那么当前已经处理的数字的个数减去当前数字的下标的前缀和即为以该数字为较小数的逆序对的个数。

因为减去当前数字下标的前缀和即为减去所有小于这个数的个数，而已经在之前出现的小于等于该数的数显然不能与该数组成逆序对，所以该点对答案的贡献。

假如是倒序，那么就是当前数字前一个数字的前缀和即为对答案的贡献。这很显然，因为是倒序，所以出现过就相当于在当前元素的后面，也就是产生了逆序对，数字要减一是因为两个相同的数字组成不了逆序对。

代码

正序代码如下：

#include<bits/stdc++.h>
#define lowbit(x) ((x)&(-x))
using namespace std;
typedef long long ll;
const int N=5e5+10;
int tr[N],rk[N],n;
ll ans;
struct point
{
    int num,val;
}a[N];
bool cmp(point x,point y)
{
    if(x.val==y.val) return x.num<y.num;
    return x.val<y.val;
}
void update(int x,int y)
{
    for(int i=x;i<=n;i+=lowbit(i))
        tr[i]+=y;
}
ll query(int x)
{
    ll sum=0;
    for(int i=x;i;i-=lowbit(i))
        sum+=tr[i];
    return sum;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].val);
        a[i].num=i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++) rk[a[i].num]=i;//离散化
    for(int i=1;i<=n;i++)
    {
        update(rk[i],1);
        ans+=i-query(rk[i]);
    }
    printf("%lld",ans);
    return 0;
}