poj 2299 树状数组求逆序对数+离散化

Ultra-QuickSort

Time Limit: 7000MS		Memory Limit: 65536K
Total Submissions: 54883		Accepted: 20184

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

Sample Output

6
0

Source

Waterloo local 2005.02.05

题意：给你长度为n个不同的数，问最少需要交换多少次使得升序只能交换相邻的两个其实就是冒泡排序的过程

题解：直接模拟的话会超时树状数组处理，n只有100000 但是0 ≤ a[i] ≤ 999,999,999

如果开树状数组的话会炸所以先离散化一下只要记录数的相对大小就可以了。求每个数的逆序数对数然后求和输出

逆序对：设A[1..n]是一个包含N个非负整数的数组。如果在i〈 j的情况下，有A〉A[j]，则(i,j)就称为A中的一个逆序对。

还有一种归并排序的写法再补

 1 /******************************
 2 code by drizzle
 3 blog: www.cnblogs.com/hsd-/
 4 ^ ^    ^ ^
 5  O      O
 6 ******************************/
 7 //#include<bits/stdc++.h>
 8 #include<iostream>
 9 #include<cstring>
10 #include<cstdio>
11 #include<map>
12 #include<algorithm>
13 #include<queue>
14 #include<cmath>
15 #define ll __int64
16 #define PI acos(-1.0)
17 #define mod 1000000007
18 using namespace std;
19 int n;
20 struct node
21 {
22     int v;
23     int pos;
24 }N[500005];
25 int a[500005];
26 int tree[500005];
27 bool cmp(struct node aa,struct node bb)
28 {
29     return aa.v<bb.v;
30 }
31 int lowbit(int t) {return t&(-t);}
32 void add(int i,int v){
33     for(;i<=n;i+=lowbit(i))
34         tree[i]+=v;
35 }
36 int sum(int i){//sum 就是统计之前有多少个小于i的数
37    int ans=0;
38    for(;i>0;i-=lowbit(i))
39     ans+=tree[i];
40    return ans;
41 }
42 int main()
43 {
44     while(~scanf("%d",&n)){
45         if(n==0)
46             break;
47         for(int i=1;i<=n;i++)
48         {
49             scanf("%d",&N[i].v);
50             N[i].pos=i;
51         }
52         sort(N+1,N+1+n,cmp);
53         for(int i=1;i<=n;i++)//离散化
54             a[N[i].pos]=i;
55         for(int i=1;i<=n;i++)//初始化
56             tree[i]=0;
57         ll ans=0;
58         for(int i=1;i<=n;i++)
59         {
60               add(a[i],1);//注意修改值为1
61               ans+=(i-sum(a[i]));
62         }
63         printf("%I64d
",ans);
64     }
65     return 0;
66 }