MnZn刚学oi,树状数组求助
查看原帖
MnZn刚学oi,树状数组求助
232507
OK咯莫名其妙楼主2021/11/17 08:47
#include<bits/stdc++.h>
using namespace std;
int n,m;
int ans=0;
int a[200005];
int c[200005];
const int mod=92084931;
struct node{
    int val,num;
}s[200005];
int lowbit(int x){
    return x&(-x);
}
void add(int x,int y){
    while(x<=n)
    {
        c[x]+=y;
        x+=lowbit(x);
    }
}
int query(int x){
    int ans=0;
    while(x>0){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
int cmp(node a,node b){
    return a.val<b.val;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]=a[i]-m;
        s[i].val=s[i-1].val+a[i];
        s[i].num=i;
    }
/*	for(int i=1;i<=n;i++)
    {
    	cout<<s[i].num<<" "<<s[i].val<<endl;
	}*/
    sort(s+1,s+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        add(s[i].num,1);
        ans+=query(s[i].num-1)%mod;
    }
    cout<<ans<<endl;
    return 0;
}
2021/11/17 08:47
加载中...