Description
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
Ultra-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.
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.
sequence.
本题的大意是求逆序对吧，只是有多组数据。大伙儿肯定习惯了归并排序；不过，我今天就是要强调的是树状数组。
---------------------------------------------我是分割线-----------------------------------------------
树状树的推导：
假设数组a[1..n]，那么查询a[1]+...+a[n]的时间是log级别的，而且是一个在线的数据结构，支持随时修改某个元素的值，复杂度也为log级别。
来观察这个图：
树状数组的结构图
令这棵树的结点编号为C1，C2...Cn。令每个结点的值为这棵树的值的总和，那么容易发现：
C1 = A1
C2 = A1 + A2
C3 = A3
C4 = A1 + A2 + A3 + A4
C5 = A5
C6 = A5 + A6
C7 = A7
C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
...
C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16
这里有一个有趣的性质：
设节点编号为x，那么这个节点管辖的区间为2^k（其中k为x二进制末尾0的个数）个元素。因为这个区间最后一个元素必然为Ax，
所以很明显：Cn = A(n – 2^k + 1) + ... + An
预备代码：
lowbit：快速求与该数相关的之前的数.
add（或change)：把x位置的值加上d（当然，其实为改变之后的值）
sum：求1-x的和。
（详细代码见下）
---------------------------------------------我是分割线-----------------------------------------------
思路：数据小的时候，我们开一个数组cnt，其范围是一组数中的最大值。cnt[i]表示数字i出现的次数（一开始清零）
我们从头操作，设每次取出的数为x，则它产生的逆序对（以它为较小者的逆序对)就是所有在此之前的比他大的数的个数。
究竟怎么表示呢？ 借鉴于前缀和，我们可以用sum(tot)（tot是最大值）-sum(x-1),这就是目前记录的比它大的数（既然已经记录过，它们一定在x的前面。然而，数据范围有很多9，我们得另想办法。观察n<=50万，我们可以把n个数映射到最多为n的数组里再进行处理。别忘了去重。
代码：
#include<stdio.h>
#include<algorithm>
using namespace std;
struct arr{long x,y;}a[500001];
long cnt[500001],tot,n,i;
long long ans;
long lowbit(long x) {return x&(-x);}
void add(long x,long d)
{
while (x<=n){cnt[x]+=d;x+=lowbit(x);}
}
long sum(long x)
{
long ans=0;
while (x>0){ans+=cnt[x];x-=lowbit(x);}
return ans;
}
bool cmp(arr a,arr b){return (a.x<b.x);}
int main()
{
scanf("%ld",&n);
while (n>0)
{
ans=0;
for (i=1;i<=n;i++)
{
scanf("%ld",&a[i].x);
if (a[i].x==a[i-1].x) a[i].y=a[i-1].y;else a[i].y=a[i-1].y+1;//a[i].x记录数据，a[i].y作为映射，在排序里排进去。
}
tot=a[n].y; //tot为数组个数，开始为最大值。
sort(a+1,a+n+1,cmp);
for (i=1;i<=tot;i++) cnt[i]=0; //清零
for (i=1;i<=n;i++)
{
ans+=sum(tot)-sum(a[i].y-1); //加上当前数产生的逆序对。
add(a[i].y,1); //修改cnt
}
printf("%lld\n",ans);
scanf("%ld",&n);
}
return 0;
}