https://atcoder.jp/contests/abc378/tasks/abc378_e
https://atcoder.jp/contests/abc378/editorial/11300
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define lowbit(x) (x)&-(x)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int N=2e5+10,mod=1e9+7;
ll n,m,k;
ll tree[N],a[N],s[N];
void update(int p){
p++;
while(p<=m){
tree[p]++;
p+=lowbit(p);
}
}
ll query(int p){
ll res=0;
p++;
while(p){
res+=tree[p];
p-=lowbit(p);
}
return res;
}
void solve(){
cin>>n>>m;
ll sum=0,res=0;
//update(0);
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=(s[i-1]+a[i])%m;
res+=s[i]*i-sum;
sum+=s[i];
res+=m*(i-1-query(s[i]));
update(s[i]);
}
cout<<res<<endl;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _=1;
//cin>>_;
while(_--) solve();
return 0;
}
标签:AtCoder,Beginner,int,res,ll,update,378,abc378,define
From: https://www.cnblogs.com/djhjojo/p/18528874