解题报告

题意：

求逆序数。

思路：

线段树离散化处理。

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#define LL long long

using namespace std;

LL sum[2001000],num[501000],_hash[501000];

void push_up(int rt)

{

    sum[rt]=sum[rt*2]+sum[rt*2+1];

}

void update(int rt,int l,int r,int p,LL v)

{

    if(l==r)

    {

        sum[rt]=+v;

        return;

    }

    int mid=(l+r)/2;

    if(p<=mid)update(rt*2,l,mid,p,v);

    else update(rt*2+1,mid+1,r,p,v);

    push_up(rt);

}

LL q_sum(int rt,int l,int r,int ql,int qr)

{

    if(ql>r||qr<l)return 0;

    if(ql<=l&&r<=qr)return sum[rt];

    int mid=(l+r)/2;

    return q_sum(rt*2,l,mid,ql,qr)+q_sum(rt*2+1,mid+1,r,ql,qr);

}

int main()

{

    int n,i,j;

    while(~scanf("%d",&n))

    {

        LL ans=0;

        if(!n)break;

        memset(_hash,0,sizeof(_hash));

        memset(num,0,sizeof(num));

        memset(sum,0,sizeof(sum));

        for(i=0; i<n; i++)

        {

            scanf("%LLd",&num[i]);

            _hash[i]=num[i];

        }

        sort(_hash,_hash+n);

        int m=unique(_hash,_hash+n)-_hash;

        for(i=0; i<n; i++)

        {

            int t=lower_bound(_hash,_hash+m,num[i])-_hash+1;

            ans+=q_sum(1,1,m,t+1,m);

            update(1,1,m,t,1);

        }

        printf("%lld\n",ans);

    }

    return 0;

}

Description

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is
sorted in ascending order. For the input sequence 

9 1 0 5 4 ,


Ultra-QuickSort produces the output 

0 1 4 5 9 .


Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

Input

Output

Sample Input

5

9

1

0

5

4

3

1

2

3

0

Sample Output

6

0

Source