[树状数组] 树状数组基础练习题题解（四）

Time Limit: 7000MS
Memory Limit: 65536K

Contents

1 Description
2 Input
3 Output
4 Sample Input
5 Sample Output
6 Source

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

Sample Output

6
0

Source

Waterloo local 2005.02.05

题目大意：求逆序对的数量
解题方法：求一个序列的逆序对数量可以转化为求对于每一个数，前面有多少个比它大的。但是本题每个数字大小较大，所以需要先将数列离散化。计算有多少个比它大的，可以通过树状数组，当前数字个数减去比它小的数字个数，就是比它大的数字个数，求和即可。

#include
#include
#include
#include
#include
#include
#define LL long long

using namespace std;

inline LL read(){
    LL x = 0;
    LL p = 1;
    char ch = getchar();

    while(ch < '0' || ch > '9'){
        if(ch == '-')
            p = -1;
        ch = getchar();
    }

    while('0' <= ch && ch <= '9'){
        x = x*10 + ch - '0';
        ch = getchar();
    }

    return x*p;
}

const LL MAXN = 500000 + 10;

struct Data{
    LL v;
    LL id;
};

inline bool cmp(Data x,Data y){
    return x.v < y.v;
}

Data input[MAXN*5];
LL tree[MAXN*5];
LL hash[MAXN*5];
LL n;

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

inline void add(LL i,LL x){
    while(i<=n){
        tree[i] += x;
        i += lowbit(i);
    }
}

inline LL sum(LL i){
    LL ans = 0;

    while(i){
        ans += tree[i];
        i -= lowbit(i);
    }

    return ans;
}

LL Sum;

int main(){

    while(scanf("%lld",&n) && n){

        memset(input,0,sizeof(input));
        memset(hash,0,sizeof(hash));
        memset(tree,0,sizeof(tree));
        Sum = 0;

        for(LL i=1;i<=n;i++){
            input[i].v = read();
            input[i].id = i;
        }

        sort(input+1,input+n+1,cmp);

        for(LL i=1;i<=n;i++)
            hash[input[i].id] = i; //离散，从小到大重新编号

        for(LL i=1;i<=n;i++){
            add(hash[i],1);
            Sum += i - sum(hash[i]);
        }

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

    }
    return 0;
}