楼上dalao解法非常清晰。蒟蒻的解法大致相同，但对于细节有些不同的处理。
为什么能够用线段树/树状数组？
我们知道，一个数产生的逆序对取决于他前面比他大的数的个数。
于是，题目转化为，每输入一个数，就将这个数对于逆序对的贡献值增加他前面比他大的数的个数，然后将这个数存下来。
答案的统计方法：
当头发长度为 (A_i) 时逆序对的数量 (=) 到 (A_i) 之前的逆序对数量 (+) 这个数所能贡献的逆序对的数量。
这个操作用树状数组会非常好实现，但是我树状数组不是特别熟，于是在比赛上选择了打线段树。
本来应该int能过，但懒得调，于是直接换成了long long
#include <iostream>
#include <algorithm>
using namespace std;
const long long MAXN = 1e5+5;
long long n,pos[MAXN],num[MAXN],seg[8*MAXN],pre;
#define lson (way<<1)
#define rson ((way<<1)+1)
#define mid (l+r)/2
void setIO(string name) {
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
ios_base::sync_with_stdio(0);
}
inline long long query(long long way, long long l, long long r ,long long qlow, long long qhigh){
if (qlow<=l && r<=qhigh) return seg[way];
if (l>qhigh || r<qlow) return 0;
return (query(lson,l,mid,qlow,qhigh)+query(rson,mid+1,r,qlow,qhigh));
}//询问 Ai+1 到 n ，也就是比 Ai 大的数的数量
inline void update(long long way, long long l, long long r, long long qlow){
if (l==r && l==qlow) {seg[way]++;return;}
if (mid>=qlow) update(lson,l,mid,qlow);
else update(rson,mid+1,r,qlow);
seg[way]++;
}//更新Ai的数量
int main(){
setIO("haircut");
cin >> n;
for (long long i=0;i<n;i++) {
cin >> pos[i];
if (pos[i]+1<=n) num[pos[i]]+=query(1,0,n,pos[i]+1,n);//询问
update(1,0,n,pos[i]);//更新
}
cout << 0 << endl;
for (long long i=1;i<n;i++){
pre+=num[i-1];//先将这个数的贡献加上
cout << pre << endl;//然后输出
}
}