POJ2299--树状数组求逆序数

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

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

Output

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

Sample Input

5

9

1

0

5

4

3

1

2

3

0

Sample Output

6

0

题目地址

题目大意

给定一个序列求逆序数,用树状数组解决,注意数据太大需离散化处理

AC代码

#include<iostream>

#include<algorithm>

#include<string.h>

#include<stdio.h>

using namespace std;

const int M=500010;

int MN;

int e[M];

int k;

struct node

{

    int val;

    int pos;

}a[M];

int lowbit(int x)

{

    return x&(-x);

}

void update(int i,int v)

{

    for(;i<=MN;i+=lowbit(i)){

        e[i]+=v;

    }

}

int getsum(int i)

{

    int res=0;

    for(;i>0;i-=lowbit(i)){

        res+=e[i];

    }

    return res;

}

bool cmp1(node a,node b)

{

    return a.val<b.val;

}

bool cmp2(node a,node b)

{

    return a.pos<b.pos;

}

void init()

{

    sort(a+1,a+k+1,cmp1);

    for(int i=1;i<=k;i++)

        a[i].val=i;

    sort(a+1,a+k+1,cmp2);

    memset(e,0,sizeof(e));

    MN=k;

}

int main()

{

    //freopen("data.in","r",stdin);

    long long  res;

    while(cin>>k&&k!=0){

        res=0;

        for(int i=1;i<=k;i++){

            cin>>a[i].val;

            a[i].pos=i;

        }

        init();

        for(int i=1;i<=k;i++){

            update(a[i].val,1);

            res+=(i-getsum(a[i].val));

        }

        cout<<res<<endl;

    }

}

巴特西