题解 | #对和#_牛客博客

考虑 $\lfloor \dfrac{a_i+a_j}{2} \rfloor = \dfrac{a_i+a_j}{2} - \{\dfrac{a_i+a_j}{2}\}$ ，于是维护 $\displaystyle \sum_{i=1}^{n}\sum_{j=i+1}^{n} \dfrac{a_i+a_j}{2} - \sum_{i=1}^{n}\sum_{j=i+1}^{n} \{\dfrac{a_i+a_j}{2}\}$ 即可，又发现等价于维护 $\dfrac{\displaystyle \sum_{i=1}^{n}\sum_{j=i+1}^{n} (a_i+a_j)}{2} - \displaystyle \sum_{i=1}^{n}\sum_{j=i+1}^{n} \{\dfrac{a_i+a_j}{2}\}$ ，对于后面这个式子，只有 $a_i \bmod 2=1,a_j \bmod 2=0$ 或者 $a_i \bmod2 = 0,a_j \bmod2 = 1$ 时才会有贡献，对于前面维护后缀和，对于后面维护后缀奇数个数和，简单合并答案即可。代码：

#include<bits/stdc++.h>
#define ll long long
#define db double
#define vec vector
#define pb push_back
#define pll pair<ll,ll>
#define mkp make_pair
#define il inline
#define endl "\n"
using namespace std;
const ll mod=998244353;
const ll inf=1e18;
ll n,a[200005],s[200005],suf[200005];
void solve(){
    cin>>n;ll ans=0;
    for(ll i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i];
    suf[n+1]=0;
    for(ll i=n;i;i--) suf[i]=suf[i+1]+(a[i]%2);
    for(ll i=1;i<n;i++) ans+=(n-i)*a[i]+s[n]-s[i];
    ans>>=1;ll res=0;
    for(ll i=1;i<n;i++){
        if(a[i]&1) res+=(n-i)-suf[i+1];
        else res+=suf[i+1];
    }
    res>>=1;
    cout<<(ans-res)<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
    ll T;cin>>T;
    while(T--) solve();
	return 0;
}