Submission #59370230

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N=5e5+10;

ll n,m,a[N];
ll s[N];

struct BIT{
    ll t[N];

    void update(int p,ll v){
        ++p;
        for(;p<=m;p+=p&-p)t[p]+=v;
    }
    ll query(int p){
        ++p;
        ll s=0;
        for(;p;p-=p&-p)s+=t[p];
        return s;
    }
    ll query(int l,int r){
        // ++l,++r;
        return query(r)-query(l-1);
    }
};

BIT t1,t2;


ll ans=0;


int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)s[i]=(s[i-1]+a[i])%m;
    for(int i=1;i<=n;i++) {
        t1.update(s[i-1],s[i-1]);
        t2.update(s[i-1],1);

        ans+=1ll*t2.query(0,s[i])*s[i]-t1.query(0,s[i]);
        // cerr<<ans<<'\n';
        ans+=1ll*t2.query(s[i]+1,m-1)*s[i]-t1.query(s[i]+1,m-1)+t2.query(s[i]+1,m-1)*m;
        // cerr<<ans<<'\n';
    }

    cout<<ans;
    return 0;
}

Submission Info

Judge Result