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
5
9
1
5
4
3
1
2
3
Sample Output
6
題意：給出一個序列，求該序列的逆序數。
首先是樹狀數組求法：
因為有5e5個值，資料範圍卻有9e9，是以要用樹狀數組求逆序數需要先進行離散化，隻有5e5個數，那麼一些較大的數可以根據其相對大小進行離散。縮減到5e5個值之内。
逆序數是根據數字輸入的先後順序，利用樹狀數組更新和檢查每次輸入一個新的數時，在其之前輸入的比他小的數的個數，即該數的逆序數。
此題中每個數都是唯一的，是以可以用數值的标号進行離散化。需要的資訊僅僅是數值的相對大小，而不是數值本身，我們将數值映射到一個小于5e5的數上，使得該數在大小上仍保持原數值性質，但是因為值變小了更利于記錄和儲存。
首先因為是利用标号進行離散，是以記錄下排序前的标号，根據數值大小進行排序，然後，周遊排序後的數組，在一個新的離散數組中，按排序好的順序記錄每個值的标号。如第一個周遊的肯定是最小的值，那麼我們再該值原先的位置a[i].i記錄下其被映射到的标号1，然後下一個值映射相對第二個值也是新的标号，2，說明其實第二小的數。将其記錄到原數值中應有的位置。實作離散化。
對于出現多個重複的數時，就不能用标号來記錄相對的大小了，因為标号是唯一的，對于一個完全相同的值，還是會被映射到大小不同的标号上，影響其相對大小。是以我們記錄一個num值表示這是第幾個不同的值，在周遊有序數組的過程中，每次遇到一個和之前不同的值，num++，并給幾個完全相同值映射。實作相同數字的離散化
#include<stdio.h>///樹狀數組求逆序數+資料離散化
#include<string.h>
#include<algorithm>
using namespace std;
struct num
{
int n,i;
}a[];
int tree[],ls[],n;
int lowbit(int x)///樹狀數組求逆序數，樹狀數組記錄某個數值是否出現過
{
return x&(-x);
}
int sum(int p)
{
int sum=;
while(p>)
{
sum+=tree[p];
p-=lowbit(p);
}
return sum;
}
void update(int p)
{
while(p<=n)
{
tree[p]++;
p+=lowbit(p);
}
}
bool cmp(num a,num b)
{
return a.n<b.n;
}
int main()///資料範圍9e9很大，但是資料元素隻有5e5個，并且每個元素唯一，是以将所有元素映射到一個5e5之内的數即是離散化，避免空間浪費
{
while(scanf("%d",&n)&&n)
{
for(int i=;i<=n;i++)
{
scanf("%d",&a[i].n);///記錄每個元素的位序，按數值大小排序，按數值從小到大周遊，将數值按位序重新标記成一個較小的數。各個數值大小關系不變
a[i].i=i;
}
sort(a+,a+n+,cmp);
for(int i=;i<=n;i++) ls[a[i].i]=i;///離散化
memset(tree,,sizeof(tree));
long long ans=;
for(int i=;i<=n;i++)
{
update(ls[i]);///按數值從小到大周遊資料，更新目前周遊數字位序的狀态，使之變成出現過
ans+=i-sum(ls[i]);///sum求和，計數在ls[i]出現之前，先出現的小于ls[i]的數的個數，這些是正常位序
}///目前周遊的數字數量i，是目前出現的數總數，用i減去正常出現的數的個數，剩餘數量就是在ls[i]出現之前
printf("%lld\n",ans);///優先出現的大于ls[i]的數值數量，這就是ls[i]的逆序數，不斷對ans累加就是結果
}
}
接觸樹狀數組兩年之後，才去看歸并排序的寫法，一直以為非常複雜，其實就是利用歸并排序的過程，模闆一點都沒改，加了句 求ans而已。
下面解釋過程：
首先是歸并排序的過程，利用了分治的思想
上圖清晰的展示了歸并排序的步驟，我們計算逆序數的過程在下方的“治”中。也就是合并數組的過程中。首先我們知道，在合并的過程中，兩個被合并的子數組是有序的通過不斷對比兩數組的值來确定合并數組的排列順序。
上圖中，展示 了合并的詳細過程，計算逆序數，即從這裡入手。i表示L區間内數組指針，j表示R區間内數組指針，現在兩區間内是有序排列，區間之間數字無序，但L區間值在R區間值左邊。若當 a【i】>a【j】時，說明a【i】以及a【i】之後的值都大于a【j】(因為有序)，并且在位置上L區間内每一個值都在其左邊，也就是說，a【j】對于mid-i+1這段區間内所有值都貢獻出了一個逆序數。是以逆序數加mid-i+1。
對于所有排序過程中符合條件的值都進行如上求和計算。總和即逆序數值。
相比樹狀數組求逆序數，歸并排序代碼簡單，不用離散化，使用友善，更加優秀。
代碼如下：
#include<bits/stdc++.h>
#define LL long long
#define M(a,b) memset(a,b,sizeof a)
using namespace std;
const int maxn=+;
int a[maxn],tmp[maxn];
int n;
LL ans;
void Meg(int l,int mid,int r)
{
int i=l,j=mid+,k=;
while(i<=mid&&j<=r)
{
if(a[i]<a[j]) tmp[k++]=a[i++];
else
{
ans+=mid-i+;///逆序數計數
tmp[k++]=a[j++];
}
}
while(i<=mid) tmp[k++]=a[i++];
while(j<=r) tmp[k++]=a[j++];
for(int i=l,k=;i<=r;k++,i++) a[i]=tmp[k];
}
void Msort(int l,int r)///歸并排序模闆
{
if(l<r)
{
int mid=(l+r)>>;
Msort(l,mid);
Msort(mid+,r);
Meg(l,mid,r);
}
}
int main()
{
while(scanf("%d",&n)&&n)
{
ans=;
for(int i=;i<=n;i++)scanf("%d",&a[i]);
Msort(,n);
printf("%lld\n",ans);
}
}