poj 2299 Ultra-QuickSort如何用树状数组高效求解逆序数？
- 内容介绍
- 文章标签
- 相关推荐
本文共计667个文字，预计阅读时间需要3分钟。
Ultra-QuickSort 时间限制：7000MS 内存限制：65536K 总提交：27736 通过：9946描述：在本题中，你需要分析一种特定的排序算法。该算法处理一个由 n 个不同整数组成的序列，通过sw…（此处省略具体步骤）。
Ultra-QuickSort
Time Limit: 7000MS
Memory Limit: 65536K
Total Submissions: 27736
Accepted: 9946
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 ,
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
59105431230
Sample Output
60
Source
Waterloo local 2005.02.05
这就是题求逆序数的题：方法有多种，最简单的用归并排序
我用的是树状数组；题目明显直接建树是不行的，因此得将其数变小，因此，用来两次快排
有个陷阱，和数据会超，得用long long 我就是因为这被ＷＡ了几次
#include<cstdio>#include<algorithm>#include<cstring>#define N 500004using namespace std;int M;long long f[N];int s[N];class node{ public: int num; int p;}root[N];int lowbit(int n){ return n&(-n);}void add(int s){ while(s<=M) { f[s]++; s+=lowbit(s); }}long long query(int num){ long long sum=0; while(num>0) { sum+=f[num]; num-=lowbit(num); } return sum;}bool cmp(node a,node b){ return a.num<b.num;}bool cmpp(node a,node b){ return a.p<b.p;}int main(){ int a; while(scanf("%d",&M)&&M) { memset(f,0,sizeof(f)); long long sum=0; for(int i=0;i<M;i++) { scanf("%d",&root[i].num); root[i].p=i; } stable_sort(root,root+M,cmp); for(int i=0;i<M;i++) root[i].num=i+1; stable_sort(root,root+M,cmpp); for(int i=0;i<M;i++) { add(root[i].num); sum+=query(M)-query(root[i].num); } printf("%lld\n",sum); }}
本文共计667个文字，预计阅读时间需要3分钟。
Ultra-QuickSort 时间限制：7000MS 内存限制：65536K 总提交：27736 通过：9946描述：在本题中，你需要分析一种特定的排序算法。该算法处理一个由 n 个不同整数组成的序列，通过sw…（此处省略具体步骤）。
Ultra-QuickSort
Time Limit: 7000MS
Memory Limit: 65536K
Total Submissions: 27736
Accepted: 9946
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 ,
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
59105431230
Sample Output
60
Source
Waterloo local 2005.02.05
这就是题求逆序数的题：方法有多种，最简单的用归并排序
我用的是树状数组；题目明显直接建树是不行的，因此得将其数变小，因此，用来两次快排
有个陷阱，和数据会超，得用long long 我就是因为这被ＷＡ了几次
#include<cstdio>#include<algorithm>#include<cstring>#define N 500004using namespace std;int M;long long f[N];int s[N];class node{ public: int num; int p;}root[N];int lowbit(int n){ return n&(-n);}void add(int s){ while(s<=M) { f[s]++; s+=lowbit(s); }}long long query(int num){ long long sum=0; while(num>0) { sum+=f[num]; num-=lowbit(num); } return sum;}bool cmp(node a,node b){ return a.num<b.num;}bool cmpp(node a,node b){ return a.p<b.p;}int main(){ int a; while(scanf("%d",&M)&&M) { memset(f,0,sizeof(f)); long long sum=0; for(int i=0;i<M;i++) { scanf("%d",&root[i].num); root[i].p=i; } stable_sort(root,root+M,cmp); for(int i=0;i<M;i++) root[i].num=i+1; stable_sort(root,root+M,cmpp); for(int i=0;i<M;i++) { add(root[i].num); sum+=query(M)-query(root[i].num); } printf("%lld\n",sum); }}