大家应该都知道什么是逆序对~~~
i>j && a[i]<a[j]
满足上述条件的数对是逆序对

假设现在有n个数，究极暴力的求逆序对的方式当然是从第1个数遍历到第n个数，对于每一个数都数一下它之前有多少个数大于它，所有的加起来就是答案。(简单直观)

考虑另一种究极暴力的方式：
假设我们知道了每个数是第几大的，这些信息记录在一个数组b中，b[i]表示原序列中i位置的数字在整个序列中是第几大的。再用另一个数组f来记录第几大的数字有多少个，也就是说f[i]表示第i大的数字的个数。
这时我们从1枚举到n，对于每一个i，我们都先将f[b[i]]加1，这时1~i这些数中第几大的数字有多少个的信息就记录在了f数组中。我们知道当前的第i个数字是第b[i]大的，这时我们计算出：第1大的、第2大的、…、第(b[i]-1)大的数字共有多少个，就计算出了(1~i)这些数中与第i个数字构成逆序对的数有多少个，同上累加起来就可~

对于每一个i，我们需要求出f[1]~f[b[i]-1]的和，(这样的计算会比较费时，因为n太大了额)
但是如果把f变成前缀和数组的话，那在更新f数组的时候，就需要将f[b[i]]~f[最后]都加一，(也很费时额)
于是我们可以把f变成树形数组来做(想偷懒了，不想写树形数组辽)，单点更新和区间查询都会好一些。(就不会那么费时辽)

代码如下(有部分注释)：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct node{
    int v,p;
};
node a[500005];
//b[i]表示原序列中第i个数是全部数字中第几大的，f[i]为上面分析的树形数组
int b[500005]={0},f[500005]={0},n=0;

bool cmp(node aa,node bb){
    return aa.v>bb.v;
}

//单点更新和区间查询操作
void add(int t){
    for(int i=t;i<=n;i+=(i&(-i)))++f[i];
}
int sum(int t){
    int res=0;
    for(int i=t;i;i-=(i&(-i)))res+=f[i];
    return res;
}

int main(){
    std::ios::sync_with_stdio(false);
    while(cin>>n&&n){
        for(int i=1;i<=n;++i)cin>>a[i].v,a[i].p=i;
        memset(f,0,sizeof(f));
        sort(a+1,a+n+1,cmp);//排序，来求每个位置的数是第几大的
        int cnt=1;//cnt用来记录当前数字是第几大的
        for(int i=1;i<=n;++i){
            if(i!=1&&a[i].v!=a[i-1].v)++cnt;
            b[a[i].p]=cnt;   //第cnt大的数字 值为a[i].v,在原序列中的位置为a[i].p，所以b[a[i].p]应等于cnt
        }
        long long int ans=0;
        for(int i=1;i<=n;++i){
            add(b[i]);  //原序列中第i个数字是第b[i]大的，更新树形数组
            ans+=sum(b[i]-1);   //求第1大~第(b[i]-1)大的数字总个数，即为与原序列中第i个数构成逆序对的数字个数
        }
        cout<<ans<<endl;
    }
    return 0;
}