时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold
题目描述 Description
给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目
数据范围：N<=105。Ai<=105。时间限制为1s。
输入描述 Input Description
第一行为n,表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。
输出描述 Output Description
所有逆序对总数.
样例输入 Sample Input
4
3
2
3
2
样例输出 Sample Output
3
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int n,m,a[100010]={0},b[100010]; 7 long long ans=0; 8 void ni(int l,int r) 9 { 10 if(l==r) return; 11 int mid=(l+r)/2; 12 ni(l,mid);ni(mid+1,r); 13 int i=l,j=mid+1,k=l; 14 while(i<=mid&&j<=r) 15 { 16 if(a[i]>a[j]) 17 { 18 b[k++]=a[j++]; 19 ans+=mid-i+1; 20 } 21 else{ 22 b[k++]=a[i++]; 23 } 24 } 25 while(i<=mid) b[k++]=a[i++]; 26 while(j<=r) b[k++]=a[j++]; 27 for(int w=l;w<=r;w++) a[w]=b[w]; 28 } 29 int main() 30 { 31 scanf("%d",&n); 32 for(int i=1;i<=n;i++) 33 { scanf("%d",&a[i]); } 34 ni(1,n); 35 printf("%lld",ans); 36 return 0; 37 }