求逆序数
时间限制：2000 ms | 内存限制：65535 KB
难度：5
- 描述
-
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
现在，给你一个N个元素的序列，请你判断出它的逆序数是多少。
比如 1 3 2 的逆序数就是1。
- 输入
- 第一行输入一个整数T表示测试数据的组数（1<=T<=5)
每组测试数据的每一行是一个整数N表示数列中共有N个元素（2〈=N〈=1000000）
随后的一行共有N个整数Ai(0<=Ai<1000000000)，表示数列中的所有元素。
数据保证在多组测试数据中，多于10万个数的测试数据最多只有一组。 - 输出
- 输出该数列的逆序数
- 样例输入
-
2 2 1 1 3 1 3 2
- 样例输出
- 0
- 1
- 分析：可以用数状数组储存每个数出现的次数，比如c[1]=3 代表目前为止 1出现了三次
- sum(a[i].val)表示小于等于它的数目 i表示目前为止总的数目
- 这样的话 i-sum(a[i].val) 就表示目前为止 大于a[i].val的数目
- 把每次的结果累加起来就可以了
- 但是这里的话数据范围较大
- 需要进行离散化，这里离散化的时候有个特点，用排序前的编号代表它们的值
- 这样的话，如果排序前已经有序，排序那么编号一定依次递增，那么对于每个编号，
- 在该编号前，大于它的，就是一对逆序数.问题就转化为了对编号进行树状数组操作
需要注意的是：排序的时候 相同的值编号靠前的先排，因为我们需要先访问编号靠前的.
#include <cstdio> #include <iostream> #include <cstring> #include <map> #include <algorithm> using namespace std; typedef long long ll; const int MAXN=1000010; int c[MAXN]; int n; int a[MAXN]; int cnt; struct node { int id; ll num; }r[MAXN]; int cmp(node x,node y) { if(x.num!=y.num) return x.num<y.num; else return x.id<y.id; } int lowbit(int x) { return x&(-x); } void add(int i,int value) { while(i<=n) { c[i]+=value; i+=lowbit(i); } } int sum(int i) { int sum=0; while(i>=1) { sum+=c[i]; i-=lowbit(i); } return sum; } int main() { int t,i,tmp; ll ans; scanf("%d",&t); while(t--) { ans=0; cnt=1; memset(c,0,sizeof(c)); memset(r,0,sizeof(r)); scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%lld",&r[i].num); r[i].num+=1; r[i].id=i; } sort(r+1,r+n+1,cmp); for(int j=1;j<=n;j++) { add(r[j].id,1); ans+=j-sum(r[j].id); } printf("%lld ",ans); } return 0; }