今日题目： 逆序对
题目描述
猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。
最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 ai>aj 且 i
Update:数据已加强。
输入格式
第一行，一个数 n，表示序列中有 n个数。
第二行 n 个数，表示给定的序列。序列中每个数字不超过 10^9。
输出格式
输出序列中逆序对的数目。
题目分析
题目难度：⭐️⭐️
题目涉及算法：树状数组，排序。
ps：有能力的小伙伴可以尝试优化自己的代码或者一题多解，这样能综合提升自己的算法能力
题解报告：
1.思路
可以用树状数组，逆序对板子解决这个问题，如果不懂的话可以去学习一下逆序对或者树状数组。
2.代码
#include <bits/stdc++.h> using namespace std; int n,a[5000002],b[5000002]; long long num=0; void merge(int l,int r) { int mid = (l+r)/2; if(l == r) { return ; } else { merge(l,mid); merge(mid+1,r); } int i = l; int j = mid + 1; int t = l; while(i<=mid&&j<=r) { if(a[i]>a[j]) { num += mid - i + 1; b[t++] = a[j]; j++; } else { b[t++] = a[i]; i++; } } while(i<=mid) { b[t++] = a[i]; i++; } while(j<=r) { b[t++]=a[j]; j++; } for(int i=l;i<=r;i++) { a[i] = b[i]; } return ; } int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } merge(1, n); printf("%lld",num); return 0; }
