题目链接

http://poj.org/problem?id=2299

解题思路

线段树求逆序对板子题

AC代码

#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long

using namespace std;
const int N=500100;
ll a[N],b[N];
int n;
ll ans;
struct TREE
{
    int l,r;
    ll sum;    
}tree[N<<2];
void Build(int i,int l,int r)
{
    tree[i].l=l;
    tree[i].r=r;
    tree[i].sum=0;
    if(l==r)
    return ;
    int mid=(l+r)>>1;
    Build(i<<1,l,mid);
    Build(i<<1|1,mid+1,r);
    tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
    return ;
}
void Update(int i,int x)
{
    if(tree[i].l==tree[i].r)
    {
        tree[i].sum++;
        return ;
    }
    if(x<=tree[i<<1].r) Update(i<<1,x);
    else Update(i<<1|1,x);
    tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
    return ;
}
int Query(int i,int l,int r)
{
    if(l<=tree[i].l && tree[i].r<=r)
    return tree[i].sum;
    if(l>tree[i].r || r<tree[i].l) return 0;
    int res=0;
    if(tree[i<<1].r>=l) res+=Query(i<<1,l,r);
    if(tree[i<<1|1].l<=r) res+=Query(i<<1|1,l,r);
    return res;
}
int main()
{
    while(scanf("%d",&n)&&n)
    {
        ans=0;//memset(tree,0,sizeof tree);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            b[i]=a[i];
        }
        sort(b+1,b+n+1);
        for(int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+n+1,a[i])-b;
        Build(1,1,n);
        for(int i=1;i<=n;i++)
        {
            Update(1,a[i]);
            ans+=i-Query(1,1,a[i]);
        }
        printf("%lld\n",ans);
    }
}