樹狀數組 +離散化。
我一開始用的 map+樹狀數組暴搞。。哪知超時了。 這題如果用樹狀數組，還是需要離散化才行。。
離散化的步驟就是， 先用一個結構體，用num 保存 原來的數，id保存原來數組所在的位置。。然後按num排序，那麼得到一個從小到大有序的序列。 然後通過id找到原數組所在的位置，並用另一個數組存放 通過映射得到的新的類似原來（比原來數組的值縮小了，但是相對應的大小關系不變）序列的數組。
[cpp]
#include <cmath>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
#include <stack>
#include <deque>
using namespace std;
typedef long long LL;
#define EPS 10e-9
#define INF 0x3f3f3f3f
#define REP(i,n) for(int i=0; i<(n); i++)
const int maxn = 500500;
int a[maxn],c[maxn],aa[maxn];
struct node{
int num,id;
bool operator <(const node & b) const {
return num<b.num;
}
}b[maxn];
int lowbit(int x){
return x&-x;
}
int add(int x){
while(x<maxn){
c[x]+=1; x+=lowbit(x);
}
}
LL sum(int x){
LL ret=0;
while(x>0){
ret+=c[x]; x-=lowbit(x);
}
return ret;
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
memset(c,0,sizeof(c));
if(n==0) break;
for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i].num=a[i],b[i].id=i;
sort(b+1,b+1+n);
aa[ b[1].id ]=1;
for(int i=2;i<=n;i++){
if(b[i].num==b[i-1].num){
aa[ b[i].id ]=aa[ b[i-1].id ];
}
else aa[ b[i].id ]=i;
}
LL ans=0;
for(int i=n;i>=1;i--){
ans+=sum(aa[i]-1);
add(aa[i]);
}
printf("%lld\n",ans);
}
return 0;
}
