Ultra-QuickSort

题目

给一个序列，我们使用冒泡排序法对它进行排序。请输出在排序过程中会进行多少次交换。

输入包含多个测试用例

每个测试用例第一行为一个整数n（n<500000）表示数组的长度
下面n行每一行包含一个整数0≤a[i]≤999,999,999，即数组中第i个元素的值。

当n=0时结束输入

对于每个输入序列，程序打印一个数op，即对给定输入序列进行排序所需的最小交换操作数。

input
```c
5
9
1
0
5
4
3
1
2
3
0

output

6
0

思路

冒泡排序是$n^2$的, 这里不能用冒泡模拟, 可以试试快排和归并。

冒泡的最小交换数就是它交换的总次数, 也就说出现 后面的数大于前面的数就算一次交换。
显然这就是求逆序对的数量, 归并可以解决：

int merge_sort(int q[], int l, int r)
{
    
	if(l >= r) return 0;
	int mid = l +r >> 1;
	int res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
	int i = l, j = mid + 1, k = l;
	while(i <= mid &&j <= r)
		if(a[i] <= a[j]) temp[k++] = a[i++];
		else {
    
			temp[k++] = a[j];
			res += j - k;
		}
	while(i <= mid) temp[k++] = a[i++];
	while(j <= r) temp[k++] = a[j++];
	
	for(i; i <= r; i++) a[i] = temp[i];
	return res;
}

换一种写法, 怎么用线段树来写呢？
当前数x, 后面任何一个大于x的都是逆序对, 即找在 x 后面 >= x的数 的数量。
先将输入的数组排序（这里就已经慢于归并写法, 图一乐）, 然后记录原数组每个元素排序后的位置。
使用线段树的 upadate 操作依次按原数组顺序插入, 但插入的位置是排序后的位置。
即 第一个插入 9 (排序后位置pos = 5), 就插入到 [5,5], 值为该位置被插入的次数。
线段树权值记录为左右子树的和。
因为插入位置是排序后的位置, 故插入到右子树的原值肯定比插入到左子树的原值大（或者等于）,所以如果插入到左子树时, 右子树有值, res就去加上右子树的值。
对于等于的情况, 可以在开始求pos时就将其化到一个位置。

如果数据范围小的话可以直接将插入的位置变成数值, 即 9 就插入到 [9,9], 省去排序操作。

代码

#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 3e6 + 10;

int t[N], a[N];
int n;
vector<int> vec;

void update(int l, int r, int u, int idx, int val, long long &res)
{
    
    if (l == r)
    {
    
        t[u]++;
        return;
    }
    int mid = l + r >> 1;
    if (idx <= mid)
    {
    
        update(l, mid, u << 1, idx, val, res);
        res += t[u << 1 | 1];
    }
    else
        update(mid + 1, r, u << 1 | 1, idx, val, res);
    t[u] = t[u << 1] + t[u << 1 | 1];
}

int main()
{
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin >> n && n != 0)
    {
    
        memset(t, 0, sizeof t);
        memset(a, 0, sizeof a);
        vec.clear();
        for (int i = 1; i <= n; i++)
        {
    
            cin >> a[i];
            vec.push_back(a[i]);
        }
        sort(vec.begin(), vec.end());
        vec.erase(unique(vec.begin(), vec.end()), vec.end());

        int pos;
        long long res = 0;
        for (int i = 1; i <= n; i++)
        {
    
            pos = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
            // cout << pos << " ";
            update(1, n, 1, pos, a[i], res);
        }
        cout << res << endl;
    }
    return 0;
}
~~~