逆序对

P1908 逆序对

题目描述

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 a_i>a_j 且 i<j的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

Update:数据已加强。

输入格式

第一行，一个数 n，表示序列中有 n个数。

第二行 n* 个数，表示给定的序列。序列中每个数字不超过 10^9。

输出格式

输出序列中逆序对的数目。

输入输出样例

输入 #1

6
5 4 2 6 3 1

输出 #1

11

说明/提示

对于所有数据，n*≤5×10⁵

请使用较快的输入输出

思路

先离散化，然后遍历，每扫一位就加入值大于当前位的个数，用树状数组计算个数

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
const int N=5e5+10;
int a[N],c[N];int n;
namespace ls { //离散模板
	const int Nn=5e6+10;
	int C[Nn],L[Nn],A[Nn];
	void ls(int *f,int *a,int n) {
		for(int i=0; i<n; i++)A[i]=a[i+1];
		memcpy(C,A,sizeof(A));
		sort(C,C+n);
		int l=unique(C,C+n)-C;
		//int l=n;
		for(int i=0; i<n; i++) {
			L[i]=lower_bound(C,C+l,A[i])-C+1;
		}
		for(int i=0; i<n; i++)f[i+1]=L[i];
	}
}
#define lowbit(x) (x)&(-(x))
void update(int x,int w){
	while(x<=n){
		c[x]+=w;
		x+=lowbit(x);
	}
}
int query(int x){
	int ret=0;
	while(x){
		ret+=c[x];
		x-=lowbit(x);
	}
	return ret;
}
signed main(){
	IOS
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	ls::ls(a,a,n);
	//for(int i=1;i<=n;i++)cout<<a[i]<<' ';
	int ans=0;
	for(int i=1;i<=n;i++){
		update(a[i],1);
		ans+=query(n)-query(a[i]);
	}
	cout<<ans;
	return 0;
}