树状数组+离散化

用树状数组求逆序数，因为这里a[i]最大达1e9而且输入数据里有0，必须要离散化。注意int溢出要用long long。
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<vector>
 8 #include<stack>
 9 #include<queue>
10 #define lson l, m, rt<<1
11 #define rson m+1, r, rt<<1|1
12 #define IO ios::sync_with_stdio(false);cin.tie(0);
13 #define INF 1e9
14 #define MAXN 500010
15 const int MOD=1e9+7;
16 typedef long long ll;
17 using namespace std;
18 ll n, c[MAXN];
19 typedef struct{
20     int v, id1, id2;
21 }Node;
22 Node node[MAXN];
23 bool cmp(const Node a, const Node b)
24 {
25     return a.v<b.v; 
26 }
27 bool cmp2(const Node a, const Node b)
28 {
29     return a.id1<b.id1; 
30 }
31 int lowbit(int t)
32 {
33     return t&(-t);
34 }
35 void add(int x, int y)
36 {
37     for(int i = x; i <= n; i += lowbit(i)){
38         c[i] += y;
39     }
40 }
41 int getsum(int x)
42 {
43     int s=0;
44     for(int i = x; i > 0; i -= lowbit(i)){
45         s += c[i];
46     }
47     return s;
48 }
49 int main()
50 {
51     IO; 
52     while(cin >> n, n){
53         ll ans=0, x;
54         memset(c, 0, sizeof(c));
55         for(int i = 1; i <= n; i++){
56             cin >> node[i].v;
57             node[i].id1 = i;//id1打标签，用于后期恢复原顺序 
58         } 
59         sort(node+1, node+n+1, cmp);//对值升序排列 
60         for(int i = 1; i <= n; i++){
61             node[i].id2 = i;//id2打标签按值从小到大，重新命名 
62         }
63         sort(node+1, node+n+1, cmp2);//通过id1恢复原顺序 
64         for(int i = 1; i <= n; i++){
65             add(node[i].id2, 1);
66             ans += i-getsum(node[i].id2);//getsum(x)表示前面<=x的个数 
67         }
68         cout << ans << endl;
69     }
70     return 0;
71 }