P1908 逆序对

思路

题目要求求出序列中所有的逆序对个数，可以转换为求每个数所有的逆序对个数之和，算单点贡献。

转化：

转化为取一个数，将这个数后面的所以数的个数记录，若这个数后面有小于它本身的数，那么答案加一。

这时就运用到区间查询功能了，考虑使用树状数组。

树状数组：

在树状数组中存储桶排结果，当然存是在这个数后面的桶排结果，并且加入树状数组，加入等价于区间加一。

此后查询区间

1

到

a_{i}-1

的所有值，即可得出答案。

由于本题数据较大，桶排需要离散化。

code:

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=7e5+5;
map<int,int>mp;
int n,a[N],b[N],c[N];
int cnt;
int lowbit(int x){
	return x&(-x);
}
void add(int x){
	while(x<=n){
		c[x]+=1;
		x+=lowbit(x);
	}
}
int get(int x){
	int ans=0;
	while(x>0){
		ans+=c[x];
		x-=lowbit(x);
	}
	return ans;
}
signed main(){
//	freopen("P1908_11.in","r",stdin);
//	freopen("P1908.txt","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	sort(a+1,a+n+1);
	int len=unique(a+1,a+n+1)-a-1;
	for(int i=1;i<=len;i++){
		mp[a[i]]=i;
	}
	for(int i=n;i>=1;i--){
		add(mp[b[i]]);
		cnt+=get(mp[b[i]]-1);
		//cout<<cnt<<endl;
	}
	cout<<cnt;
    return 0;
}

文章操作

思路

转化：

树状数组：

code:

相关推荐

评论

P1908 逆序对