求助神犇!!!(树状数组)
  • 板块灌水区
  • 楼主wwwhyj
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/6/2 17:22
  • 上次更新2024/6/2 17:34:14
查看原帖
求助神犇!!!(树状数组)
1049791
wwwhyj楼主2024/6/2 17:22

逆序对 求助为毛样例是5,感觉代码也没太有问题

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int n,m,a[maxn],b[maxn],c[maxn];
int lowbit(int x){
	return x&(-x);
}
void add(int x,int y){
	for(;x<=n;x+=lowbit(x))c[x]+=y;
}
int ask(int x){
	int y=0;
	for(;x;x-=lowbit(x))y+=c[x];
	return y;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",a+1);
		b[i]=a[i];
	}
	sort(b+1,b+n+1);
	m=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+m+1,a[i])-b;
	long long ans=0;
	for(int i=1;i<=n;i++){
		add(a[i],1);
		ans+=ask(m)-ask(a[i]);
	}
	cout<<ans;
	return 0;
}
2024/6/2 17:22
加载中...