title: 题目
给一个序列，我们使用冒泡排序法对它进行排序。请输出在排序过程中会进行多少次交换。
输入包含多个测试用例
每个测试用例第一行为一个整数n（n<500000）表示数组的长度
下面n行每一行包含一个整数0≤a[i]≤999,999,999，即数组中第i个元素的值。
当n=0时结束输入
对于每个输入序列，程序打印一个数op，即对给定输入序列进行排序所需的最小交换操作数。
title: input
5
9
1
0
5
4
3
1
2
3
0
title: output
6
0
title: 思路
冒泡排序是$n^2$的, 这里不能用冒泡模拟, 可以试试快排和归并。
冒泡的最小交换数就是它交换的总次数, 也就说出现 后面的数大于前面的数就算一次交换。
显然这就是求逆序对的数量, 归并可以解决：
~~~ c ++
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], 省去排序操作。
title:代码
~~~ c ++
#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;
}
~~~