• 给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。每个数字不超过1e9。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int n, m;
int a[N];
int tr[N];
vector<int>lan;
int lowbit(int x){
	return x&(-x);
}
void discrete()
{
    sort(lan.begin(), lan.end());   //排序
    lan.erase(unique(lan.begin(), lan.end()), lan.end());   //去重
}

//查询
int find(int x)
{
    return lower_bound(lan.begin(), lan.end(), x)-lan.begin()+1;  //返回所查询的数据的下标
}
void add(int x,int c){
	for(int i=x;i<=n;i+=lowbit(i))tr[i]+=c;
}

int query(int x){
	int res=0;
	for(int i=x;i;i-=lowbit(i))res+=tr[i];
	return res;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	
	for(int i=1;i<=n;i++)lan.push_back(a[i]);
	discrete();
	int mx=lan.size();
	ll cnt=0;
	for(int i=1;i<=n;i++){
		cnt+=query(mx)-query(find(a[i]));
		add(find(a[i]),1);
	}
	cout<<cnt<<endl;
}