UVA10810 Ultra-QuickSort

题意

给出 $n$ 个数，求逆序对个数。

其中 $n\le 500000$ ，每个数 $\le 999,999,999$ 。

题解

数的范围很大，所以直接用树状数组肯定不行。但事实上我们只关心数之间的顺序，所以排序后用 $\text{ord[]}$ 记录顺序即可。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct node {
    ll id,s;
} s[500005];
ll n,t[500005],ord[500005];

inline void init() { memset(t,0,sizeof(t)); }

inline bool cmp(const node &x,const node &y) { return x.s<y.s; }

inline ll lowbit(ll x) { return x&-x; }

inline void add(ll x,ll y) { for (;x<=n;x+=lowbit(x)) t[x]+=y; }

inline ll query(ll x)
{
    ll ans=0;
    for (;x;x-=lowbit(x)) ans+=t[x];
    return ans;
}

signed main()
{
    while (~scanf("%lld",&n) && n)
    {
        init();
        for (ll i=1;i<=n;i++) s[i].s=read(),s[i].id=i;
        sort(s+1,s+n+1,cmp);
        for (ll i=1;i<=n;i++) ord[s[i].id]=i;
        ll ans=0;
        for (ll i=n;i;i--)
        {
            ans+=query(ord[i]-1);
            add(ord[i],1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}