POJ-2299(树状数组+离散化)

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

这道题是树状数组的入门题　所以恭喜我们又要学习并开始运用到一个有意思的数据结构了

1. 题意
   按照白话来说就是现在有一个无序序列　我们只能交换相邻元素　把无序序列变成升序排列　求最小步数

2. 分析
   对于这道题的分析是两个方面　首先我们需要转化问题　即题到底想让我们干什么　我们仔细观察不难发现　我们要做的就是计算每一个数前面大于它本身的数有多少　即逆序数　这就把问题转化为了一个区间求和问题　这就是树状数组的强项　我们可以在O(logn)内完成　大致思路就是这样　我们又发现了一个问题　就是数据范围很大　即[0,999999999]　显然我们要以数字大小为数组下标　而且这题与数字本身并没有什么太大联系　所以自然而然想到离散化　这题到这里就结束了　注意数字最多五十万　即最大答案数超过int范围　开long long 即可

3. 总结
   BIT是一个优秀的数据结构　虽然比不上线段树　但是胜在代码简洁　有了思路短时间即可完成　所以需要花费一些时间来训练

AC代码

#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<vector>
#include<cstdlib>
#include<utility>
#include<cstring>
#include<cstdio>
using namespace std;

typedef long long ll;
struct node{
    int w,index;
    bool operator<(const node &tmp)const{
        return w<tmp.w;
    }
};
ll m,n,num;
ll bit[500010];
node book[500010];

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

ll add(ll x){
    for(int i=x;i<=500010;i+=lowbit(i)){
        bit[i]+=1;
    }
}

ll sum(ll x){
    ll ans = 0;
    for(int i=x;i>0;i-=lowbit(i)){
        ans+=bit[i];
    }
    return ans;
}

int main()
{
    while(cin >> m && m){
        num = 0;
        memset(bit,0,sizeof(bit));
        for(int i=1;i<=m;++i){
            cin >> n;
            book[i].w = n;
            book[i].index = i;
        }
        sort(book+1,book+1+m);
        for(int i=m;i>=1;--i){
            num+=sum(book[i].index); //利用从后往前排除离散化留下的同一个数字离散为不同数字的情况　代码量少一点
            add(book[i].index);//再或者就是离散化费点事　同一个数字为离散为相同的值　就可以前后都ok了　总之就是好想不好写　好写不好想
        }
        cout << num << endl;
    }
    return 0;
}