离散化+ 逆序数 用树状数组。
知道怎么求逆序数和离散化就是个模板题
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <string>
using namespace std;
typedef __int64 ll;
int const MAXN = 500010;
int c[MAXN * 2];
int n;
struct Num{
int val,pos;
}num[MAXN];
int LowBit(int x){
return x & (-x);
}
void Add(int x,int d){
while(x <= MAXN * 2){
c[x] += d;
x += LowBit(x);
}
}
int Sum(int x){
int ret = 0;
while(x > 0){
ret += c[x];
x -= LowBit(x);
}
return ret;
}
bool cmp(Num a,Num b){
return a.val < b.val;
}
int main(){
while(~scanf("%d",&n),n){
memset(c,0,sizeof(c));
for(int i = 1;i <= n;i++){
scanf("%d",&num[i].val);
num[i].pos = i;
}
sort(num + 1,num + n + 1,cmp);
ll sum = 0;
for(int i = 1;i <= n;i++){
Add(num[i].pos,1);
sum += i - Sum(num[i].pos);
}
printf("%I64d\n",sum);
}
return 0;
}