题意：求冒泡排序的交换次数，即求逆序数，即求对于每个数前面有多少个数比他大，n < 500,000，0 ≤ a[i] ≤ 999,999,999。
题解：因为值较大，个数较少，所以我们把每个元素进行映射，比如50,20,30,16，就映射为4,2,3,1这种。先记录下标然后sort排序后用rank数组记录每个数最后所在的位置，rank数组里存的值就是映射后的值，更新加查询即可。减树可以用n或者用N，但是要保证先后关系一致性，不能build用n，查询用N。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
using namespace std;
#define m ((l+r)>>1)
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define N 500005
int rank[N];
struct node
{
int id,val;
}num[N];
bool cmp(node n1,node n2)
{
return n1.val<n2.val;
}
struct Tree
{
int l,r,sum;
}tree[N<<];
void build(int rt,int l,int r)
{
tree[rt].l=l;
tree[rt].r=r;
tree[rt].sum=;
if(l==r) return;
build(lson);
build(rson);
}
void update(int rt,int l,int r,int data)
{
tree[rt].sum++;
if(l==r) return;
if(data<=m) update(lson,data);
else update(rson,data);
}
int query(int rt,int l,int r,int ll,int rr)
{
if(l>=ll&&r<=rr) //查询区间包含当前区间
{
return tree[rt].sum;
}
int sum=;
if(ll<=m) sum+=query(lson,ll,rr);
if(rr>m) sum+=query(rson,ll,rr);
return sum;
}
//这是以前的查询写法 感觉上面的更好
/*
int query(int rt,int l,int r,int ll,int rr)
{
if(llz==l&&rr==r)
{
return tree[rt].sum;
}
if(rr<=m) return query(lson,ll,rr);
else if(ll>m) return query(rson,ll,rr);
else return query(lson,ll,m)+query(rson,m+1,rr);
}
*/
int main()
{
// freopen("cin.txt","r",stdin);
int n;
while(scanf("%d",&n)&&n)
{
for(int i=;i<=n;i++)
{
scanf("%d",&num[i].val);
num[i].id=i;
}
sort(num+,num+n+,cmp);
for(int i=;i<=n;i++) rank[num[i].id]=i;
//id相当于开学的排名12345 rank相当于期末的排名
//那么sum就是经过这学期每个人超越的人的个数的和
//也就是说越靠后的人超越的人的可能性越高
//sort前的id x==num[i].id x和i都表示开学的排名
//sort后的id x==num[i].id x表示开学排名 i表示期末排名
//所以就是rank[x]=i 开学排名为x的人的期末排名为i
//也就是说初始时下标为x的人的现在的下标是i
build(,,N);
long long sum=;
for(int i=;i<=n;i++)
{
int x = rank[i];//元素最后所在的位置
//printf("%d***\n",i);
sum+=query(,,N,x,N);//统计这个数前面有多少个比他大的数
update(,,N,x);//把这个数加到树中
}
printf("%lld\n",sum);
}
return ;
}