MnZn树状数组求助,输出为负
查看原帖
MnZn树状数组求助,输出为负
737158
yszkddzyh楼主2023/2/18 16:08

rt,65pts,提交记录

#include <iostream>
#include <algorithm>
#define mod 92084931ll
#define int long long
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn=2e6+5;
struct node{
	int v,id;
	friend bool operator<(node a,node b){
		if(a.v==b.v) return a.id<b.id;
		return a.v<b.v;
	}
}a[maxn];
int n,m,l,b[maxn],c[maxn],s;
void add(int p,int k){
	for(;p<=n;p+=lowbit(p))
		c[p]=c[p]+k;
}
int sch(int p){
	int cnt=0;
	for(;p;p-=lowbit(p))
		cnt=cnt+c[p];
	return cnt;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i].v),
		a[i].v+=a[i-1].v-m,
		a[i].id=i;
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
		if(a[i].v==a[i-1].v) b[a[i].id]=b[a[i-1].id];
		else b[a[i].id]=i;
	for(int i=n;i;i--)
		add(b[i],1),s=(s+(a[i].v>0)+i-sch(b[i]))%mod;
	printf("%lld",s%mod);
	return 0;
}
2023/2/18 16:08
加载中...