frosh week HDU 树状数组求逆序数

本文主要是介绍frosh week HDU 树状数组求逆序数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

解析看这里一文教你树状数组如何求逆序数https://blog.csdn.net/zlq7777/article/details/122417173

 ans+=i-getsum(t[i].id);sum += query(reflect[i]) - 1;都行，两种逆序数计数方法选择而已

#include<bits/stdc++.h>
using namespace std;
int n;
typedef long long ll;
int reflect[1000005],c[1000005];
struct node{
	int val;
	int pos;
}a[1000005];
bool cmp(node a,node b){
	return a.val<b.val;
}
int lowbit(int x){
	return x&(-x);
}
int update(int i,int k){
	while(i<=n){
		c[i]+=k;
		i+=lowbit(i); 
	}
}
int getsum(int i){
	int ans=0;
	while(i>0){
		ans+=c[i];
		i-=lowbit(i); 
	}
	return ans;
}
int main(){
	while(~scanf("%d",&n)){
		memset(c,0,sizeof(c));
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i].val);
			a[i].pos=i;
		}
		sort(a+1,a+1+n,cmp);
		ll ans=0;
		for(int i=n;i>=1;i--){
			update(a[i].pos,1);
			ans+=getsum(a[i].pos)-1;
		}
		printf("%lld\n",ans);
	}
}

这篇关于frosh week HDU 树状数组求逆序数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！