题目描述
猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。
最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 ai>aja_i>a_jai>aj 且 i<ji<ji<j 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。
Update:数据已加强。
输入格式
第一行，一个数 nnn，表示序列中有 nnn个数。
第二行 nnn 个数，表示给定的序列。序列中每个数字不超过 10910^9109。
输出格式
输出序列中逆序对的数目。
输入输出样例
输入 #1 复制
6
5 4 2 6 3 1
输出 #1 复制
11
这个题可以用线段树写，但树状数组写起来更优雅一些。数据加强后可以作为树状数组+离散化的板子题了。看到数据范围我们知道常规的桶肯定是不行的，1e9直接MLE，那么需要离散化一下。这里我用的是结构体存储原数和其初始位置，然后对结构体数组从小到大sort一遍。此时开辟一个新的数组rank。比较关键的部分是：
for(i=1;i<=n;i++)
{
rank[p[i].x]=i;
}
rank数组也相当一个桶，只不过桶的大小不必为1e9了，只需5e5即可。这样得到的新的rank数组实际上和原数组是等价的，只不过数的绝对大小变成了相对大小。然后利用树状数组处理。但这样其实有一个问题，就是数据可能是重复的。解决方法有2：一是用stable_sort排序，外加cmp函数里取等号；二是cmp函数中如果两个结构体数值相等，那么按照位置大小排序。这样的话即使两个数相等，也会使得分配后的大小能确保不会对逆序数的计算产生影响。
#include <bits/stdc++.h> using namespace std; int ans=0,n,i; int t[500005],rank[500005]; struct point { int num; int x; }p[500005]; bool cmp(point a, point b) { if(a.num != b.num) return a.num < b.num; return a.x < b.x; } void add(int x, int y) { for( ; x <= n; x += x & (-x)) t[x] += y; } int ask(int x) { int ans=0; for(; x; x -= x & -x) ans += t[x]; return ans; } int main() { cin>>n; int i; long long cnt=0; for(i=1;i<=n;i++) { scanf("%d",&p[i].num); p[i].x=i;//位置 } sort(p + 1, p + n + 1, cmp);//按照原数排序 for(i=1;i<=n;i++) { rank[p[i].x]=i; } for(i=1;i<=n;i++) { cnt += 0ll + ask(n) - ask(rank[i]); add(rank[i], 1); } cout<<cnt; return 0; }