POJ 2299 Ultra-QuickSort

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 ,

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

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

题意

因为是相邻的两个数两两交换，变成一个规定顺序的序列，相当于求一个序列的逆序数

思路

思路出处 https://blog.csdn.net/summer__show_/article/details/52043126

我觉得他的代码不是按照他讲的写的

转化为线段树：

我们先将原数组每个值附上一个序号pos，再将它排序。如题目的例子：

v： 9 1 0 5 4

pos： 1 2 3 4 5

排序后：

v： 0 1 4 5 9

pos： 3 2 5 4 1

然后由于排序后num为0的点排在原来数组的第3个，所以为了将它排到第一个去，那就至少需要向前移动两次，同时它也等价于最小的数0之前有2个数比它大（所以要移动两次），将0移到它自己的位置后，我们将0删掉（目的是为了不对后面产生影响）。再看第二大的数1，它出现在原数组的第二个，他之前有一个数比它大所以需要移动一次。这样一直循环下去那么着5个数所需要移动的次数就是：

v： 0 1 4 5 9

次数 2 1 2 1 0

将次数全部要加起来就是最后所需要移动的总次数

关键

线段树区间节点的值存的是：此区间内元素的个数。由于有元素被删去，所以需要每次更新。

Code

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

long long sum;///记住 >= 2 个int相加可超int
struct node
{
    int L, R, val;
}a[N << 2];

struct edge
{
    int v, pos;
}b[N];

bool cmp(edge a, edge b)
{
    return a.v < b.v;
}

void init(int num, int l, int r)
{
    a[num].L = l;
    a[num].R = r;
    a[num].val = 0;

    if(l == r)
    {
        a[num].val = 1;
        return ;
    }

    int mid = (l + r) >> 1;
    init(num << 1, l, mid);
    init(num << 1 | 1, mid + 1, r);

    a[num].val = a[num << 1].val + a[num << 1 | 1].val;
}

void update(int num, int pos)
{
    if(a[num].L == a[num].R && a[num].L == pos)
    {
        a[num].val = 0;///所谓删掉
        return ;
    }

    int mid = (a[num].L + a[num].R) >> 1;
    if(mid >= pos)
        update(num << 1, pos);
    else
        update(num << 1 | 1, pos);

    a[num].val = a[num << 1].val + a[num << 1 | 1].val;
}

///num为当前区间编号，l、r为查询区间边界
int query(int num, int l, int r)
{
    if(l > r)
        return 0;

//    cout << "目标区间 ：" << l << ' ' << r << '\n';
    int sum = 0;
    if(a[num].L == l && a[num].R == r)
    {
//        cout << "找到了 " << l << ' ' << r << ' ' << a[num].val << '\n';
        return a[num].val;
    }

    int mid = (a[num].L + a[num].R) >> 1;
    if(mid >= r)
        sum += query(num << 1, l, r);///明确要找什么、去哪找
    else if(mid < l)
        sum += query(num << 1 | 1, l, r);
    else
        sum += query(num << 1, l, mid) + query(num << 1 | 1, mid + 1, r);
    return sum;
}

int main()
{
    int n;
    while(~scanf("%d", &n) && n)
    {
        init(1, 1, n);
//        for(int i = 1; i <= 2 * n - 1; ++i)
//            cout << i << ' ' << a[i].L << ' ' << a[i].R << ' ' << a[i].val << '\n';
        sum = 0;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &b[i].v);
            b[i].pos = i;
        }
        sort(b + 1, b + 1 + n, cmp);
//        for(int i = 1; i <= n; ++i)
//            cout << b[i].v << ' ' << b[i].pos << '\n';
//        cout << '\n';
        for(int i = 1; i <= n; ++i)
        {
            int tem = query(1, 1, b[i].pos - 1);
//            cout << "查询值 ： " << b[i].v << " 位置 ： " << b[i].pos << " 查询区间 ： " << "1 ~ " << b[i].pos - 1 << ' ' << tem << '\n';
            sum += tem;
            update(1, b[i].pos);
        }
        cout << sum << '\n';
    }
}