Ultra-QuickSort 求最小交换次数即求逆序对数树状数组+离散化

素颜马尾好姑娘i 2022-06-13 08:45 240阅读 0赞

首先介绍一下树状数组

树状数组(binary indexed tree)，是一种设计新颖的数组结构，它能够高效地获取数组中连续n个数的和。概括说，树状数组通常用于解决以下问题：数组\{a\}中的元素可能不断地被修改，怎样才能快速地获取连续几个数的和？

传统数组(共n个元素)的元素修改和连续元素求和的复杂度分别为O(1)和O(n)。树状数组通过将线性结构转换成伪树状结构（线性结构只能逐个扫描元素，而树状结构可以实现跳跃式扫描），使得修改和求和复杂度均为O(lgn)，大大提高了整体效率。

图就不上了，举个简单的例子

C1 = A1 C2 = A1 + A2  C3 = A3  C4 = A1 + A2 + A3 + A4

C5 = A5 C6 = A5 + A6  C7 = A7  C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8

C\[i\]=A\[i\]+A\[i-1\]+....+A\[i-2^k+1\] 其中的k是

设节点编号为x，那么这个节点管辖的区间为2^k（其中k为x二进制末尾0的个数）个元素。

算这个2^k有一个快捷的办法，定义一个函数如下即可

`int` `lowbit(` `int` `x){`

`return` `x&(x^(x–1));`

`}`

比较常用的是

int lowbit(int x)

return x& (-x);

那么该题的题意如下

描述

Ultra-QuickSort算法处理一个由n个不相同整数组成的序列，通过交换序列中相邻两个整数从而使得序列达到升序排列。

比如输入：

9 1 0 5 4

Ultra-QuickSort算法给出输出：

0 1 4 5 9

请算出Ultra-QuickSort算法需要进行多少次交换操作

输入

输入数据包括多个case。每个case第一行是一个正整数 n < 500,000 ，表示输入长度，后面n行，每行是一个 999,999,999 以内的非负整数。  
  
输入以n=0结束

输出

每个case一行，表示交换操作的次数。

样例输入

5
    9
    1
    0
    5
    4
    3
    1
    2
    3
    0

样例输出

6
    0

来源  
会发现这个题就是求该数组的逆序对数，那么该怎么求呢？首先发现虽然最多只有500000个数，但是每个数可能会非常的大999999999这么大，所以就会很尴尬，那么我么需要把它离散化，在离散化之后，最多只有500000个数了，然后我们开一个500000的数组，按输入顺序插入数字，每次插入的时候可以算一下比这个数组中比该数字小的个数sum(i)，然后用i-sum(i)就是目前不符合规定的逆序对，最后把这些加起来就是总的逆序对数 举个例子

假设输入的数组是9 1 0 5 4， 离散后的结果aa\[\] = \{5,2,1,4,3\};

在离散结果中间结果的基础上，那么其计算逆序数的过程是这么一个过程。

1，输入5， 调用upDate(5, 1),把第5位设置为1

1 2 3 4 5

0 0 0 0 1

计算1-5上比5小的数字存在么？ 这里用到了树状数组的getSum（5） = 1操作，

现在用输入的下标1 - getSum(5) = 0 就可以得到对于5的逆序数为0。

2. 输入2， 调用upDate(2, 1),把第2位设置为1

1 2 3 4 5

0 1 0 0 1

计算1-2上比2小的数字存在么？ 这里用到了树状数组的getSum（2） = 1操作，

现在用输入的下标2 - getSum(2) = 1 就可以得到对于2的逆序数为1。

3. 输入1， 调用upDate(1, 1),把第1位设置为1

1 2 3 4 5

1 1 0 0 1

计算1-1上比1小的数字存在么？ 这里用到了树状数组的getSum（1） = 1操作，

现在用输入的下标 3 - getSum(1) = 2 就可以得到对于1的逆序数为2。

4. 输入4， 调用upDate(4, 1),把第5位设置为1

1 2 3 4 5

1 1 0 1 1

计算1-4上比4小的数字存在么？ 这里用到了树状数组的getSum（4） = 3操作，

现在用输入的下标4 - getSum(4) = 1 就可以得到对于4的逆序数为1。

5. 输入3， 调用upDate(3, 1),把第3位设置为1

1 2 3 4 5

1 1 1 1 1

计算1-3上比3小的数字存在么？ 这里用到了树状数组的getSum（3） = 3操作，

现在用输入的下标5 - getSum(3) = 2 就可以得到对于3的逆序数为2。

6. 0+1+2+1+2 = 6 这就是最后的逆序数

那么最后看一下代码 // ConsoleApplication1.cpp : 定义控制台应用程序的入口点。  
//  
  
  
\#include "stdafx.h"  
\#include<iostream>  
\#include<algorithm>  
\#include<stdio.h>  
using namespace std;  
int n;  
struct node  
\{  
int val, order;  
bool operator < (const node & x)  
\{  
return val < x.val;  
\}  
\}c\[500010\];  
int a\[500010\];  
int t\[500010\];  
int lowbit(int x)  
\{  
return x&(-x);  
\}  
void add\_t(int x)  
\{  
while (x <= n)  
\{  
t\[x\] += 1;  
x += lowbit(x);  
\}  
\}  
int get\_sum(int x)  
\{  
int res=0;  
while (x > 0)  
\{  
res += t\[x\];  
x -= lowbit(x);  
\}  
return res;  
\}  
int main()  
\{  
long res;  
while (1)  
\{  
memset(t, 0, sizeof(t));  
//scanf("%d", &n);  
cin >> n;  
if (n == 0) break;  
for (int i = 1; i <= n; i++)  
\{  
cin >> c\[i\].val; //scanf("%d", &c\[i\].val);  
c\[i\].order = i;  
\}  
sort(c + 1, c+1+n);  
/\*  
debug  
for (int i = 1; i <= n; i++)  
cout << " " << c\[i\].val;  
cout << endl;  
debug  
\*/  
for (int i = 1; i <= n; i++)  
a\[c\[i\].order\] = i;  
  
  
/\*  
for (int i = 1; i <= n; i++)  
cout << " " << a\[i\];  
cout << endl;  
\*/  
res = 0;  
for (int i = 1; i <= n; i++)  
\{  
add\_t(a\[i\]);  
res += i - get\_sum(a\[i\]);  
\}  
cout << res << endl;  
\}  
return 0;  
\}