求助dalao,树状数组求逆序对哪里有锅
查看原帖
求助dalao,树状数组求逆序对哪里有锅
379758
晨曦时雨楼主2022/9/9 08:41
#include<iostream>
#include<algorithm>
using namespace std;
const int N=200010;
const int MOD=92084931;
int a[N],b[N],s[N],p[N],tree[N];
int n,m,ans;
bool cmp(int x,int y){
	return s[x]<s[y];
}
int lowbit(int x){
	return x&(-x);
}
int ask(int x){
	int num=0;
	while(x>0){
		num+=tree[x];
		x-=lowbit(x);
	}
	return num;
}
void add(int x,int d){
	while(x<=n+1){
		tree[x]=(tree[x]+d)%MOD;
		x+=lowbit(x);
	}
}
int main(){
	cin>>n>>m;
	s[0]=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]-=m;
		s[i]=a[i]+s[i-1];
		p[i]=i;
	}
	for(int i=1;i<=n;i++) if(s[i]>0) ans++;
	stable_sort(p+1,p+n+1,cmp);
	for(int i=1;i<=n;i++) s[p[i]]=i;
	for(int i=1;i<=n;i++){
		ans+=ask(s[i]-1);
		ans%=MOD;
		add(s[i],1);
	}
	cout<<ans%MOD;
	return 0;
}
2022/9/9 08:41
加载中...