Ultra
任意给定一个集合 s, 如果用 t[val] 保存数值 val 在集合 s 中出现的次数, 那么数组 t 在[l, r]上的区间和就表示集合 s 中范围在 [l, r] 内的数有多少个.
在集合 s 的数值范围上建立一个树状数组, 来维护 t 的前缀和. 这样即使在集合 s 中插入或删除一个数, 也可以高效地进行统计.
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 sequenceUltra-QuickSort produces the output
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
/*离散化 + 树状数组没有用归并------(马桶塞子是亮点啊)
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAX_N = 5e5 + 500;
int n;
int arr[MAX_N];
struct BIT{int * bit;// bit[i] 表示i在bit数组中出现的次数int _size;BIT(int n): _size(2 * n){// 防止越界bit = new int[_size]();// 默认初始化}~BIT(){delete [] bit;}void add(int i, int val){// 单点修改for(; i <= _size;){bit[i] += val;i += i & -i;}}int ask(int i){// 查询前缀和int sum = 0;for(; i > 0;){sum += bit[i];i -= i & -i;}return sum;}
};
vector<int> num_discrete;// 离散化数组
void compress(){// 离散化sort(num_discrete.begin(), num_discrete.end());num_discrete.erase(unique(num_discrete.begin(), num_discrete.end()), num_discrete.end());for(int i = 0; i < n; ++i){arr[i] = lower_bound(num_discrete.begin(), num_discrete.end(), arr[i]) - num_discrete.begin() + 1;}
}
int main(){while(scanf("%d", &n) && n != 0){{// 保证离散化数组是新的vector<int> trash;num_discrete.swap(trash);}// printf("DISCRETE:\t%lu\n", num_discrete.size());for(int i = 0; i < n; ++i){scanf("%d", arr + i);num_discrete.push_back(arr[i]);}compress();// for(int i = 0; i < n; ++i){// printf(" %d", arr[i]);// }// puts("");BIT bit(num_discrete.size());long long ans = 0;for(int i = 0; i < n; ++i){int cnt = bit.ask(num_discrete.size()) - bit.ask(arr[i]);ans += cnt;bit.add(arr[i], 1);}printf("%lld\n", ans);}return 0;
}