猫猫TOM和小老鼠JERRY最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。最近，TOM老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中ai>aj且i<j的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。
Update:数据已加强。
第一行，一个数n，表示序列中有n个数。
第二行n个数，表示给定的序列。序列中每个数字不超过10910^9109
输出格式：给定序列中逆序对的数目。
对于25%的数据，n≤2500n \leq 2500n≤2500
对于50%的数据，n≤4×104n \leq 4 \times 10^4n≤4×104。
对于所有数据，n≤5×105n \leq 5 \times 10^5n≤5×105
请使用较快的输入输出
应该不会n方过50万吧 by chen_zhe
【解题思路】
这一道题跟最接近神的人没有任何区别，可以直接看以前的博客，略
树状数组求逆序对
【code】
1 #include <cstdio>
2 #include <algorithm>
3 #include <iostream>
4 using namespace std;
5 int n,a[500005],p[500005],tree[500005];
6 long long ans=0;
7 inline bool cmp(int x,int y){
8 return a[x]<a[y];
9 }
10 inline int lowbit(int x){
11 return x&(-x);
12 }
13 inline int GetSum(int x){
14 int ans=0;
15 for(register int i=x;i!=0;i-=lowbit(i))
16 ans+=tree[i];
17 return ans;
18 }
19 inline void Add(int x){
20 for(register int i=x;i<=n;i+=lowbit(i))
21 tree[i]+=1;
22 return ;
23 }
24 int main(){
25 scanf("%d",&n);
26 for(int i=1; i<=n; i++) {
27 scanf("%d",&a[i]);
28 p[i]=i;
29 }
30 stable_sort(p+1,p+n+1,cmp);
31 for(int i=1; i<=n; i++)
32 a[p[i]]=i;
33 for(int i=n; i>=1; i--){
34 ans+=GetSum(a[i]-1);
35 Add(a[i]);
36 }
37 printf("%lld\n",ans);
38 return 0;
39 }
原文：https://www.cnblogs.com/66dzb/p/11202922.html