树状数组 解 POJ 2299 Quick-Sort

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.

题目链接 http://poj.org/problem?id=2299

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

思路

要查询出当前数字前面有几个比他大的数字，我们可以反着求，用前面的数字个数 - 比当前数字小的个数。而这个小的个数就是用树状数组的查询，开始时，我们把tree数组初始化为0，每当查询完毕一个数，我们就把tree[这个数]加一，这样我们只需要看看当前数字前面总共有多少个1就行了

原文链接 https://blog.csdn.net/weixin_43918531/article/details/87950037

树状数组 https://www.cnblogs.com/hsd-/p/6139376.html

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 500005;

struct node
{
    int val, pos, num;///pos :输入时的先后顺序
                      ///num :由小到大的先后顺序
}a[N];
int tree[N];

int n;
long long sum;

bool cmp_val(node a, node b)
{
    return a.val < b.val;
}

bool cmp_pos(node a, node b)
{
    return a.pos < b.pos;
}

int lowbit(int x)///得到x最低位1（后面补零）所代表的数
{
    return ( x & (- x) );
}

void update(int pos)///单点更新（向上）
{
    for(int i = pos; i <= n; i += lowbit(i))
        tree[i]++;
}

int query(int pos)///区间查询（向下）
{
    int tem = 0;
    for(int i = pos; i >= 1; i -= lowbit(i))
        tem += tree[i];
    return tem;
}

int main()
{
//    freopen("in.txt", "r", stdin);

    while(~scanf("%d", &n) && n)
    {
        sum = 0;
        memset(tree, 0, sizeof(tree));
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &a[i].val);
            a[i].pos = i;
        }
        sort(a + 1, a + 1 + n, cmp_val);///从小到大排序
        for(int i = 1; i <= n; ++i)
            a[i].num = i;
        sort(a + 1, a + 1 + n, cmp_pos);///按输入顺序排序

        ///这个遍历过程需要其输入时的位置和其大小位置
        for(int i = 1; i <= n; ++i)
        {///i代表输入先后顺序，a[i].num代表大小顺序（由小到大）
            sum += i - 1 - query(a[i].num);
            update(a[i].num);
        }
        cout << sum << '\n';
    }
    return 0;
}