题解 | #进退的艺术#

排序后，对于一个数 $a[i]$ ，寻找第一个满足 $a[i]+a[x]>m$ 的 $x$ 。

此时 $x$ 左边的都是不会发生冲突的，对 $a[i]$ 自己的贡献是 $(x-1)\times a[i]$

此时 $x$ 和 $x$ 右边的都是会发生冲突的，对 $a[i]$ 自己的贡献是 $\sum_{i=x}^{n} a[i]=S[n]-S[x-1]$

但这里麻烦是，左右两边可能包含自己。然后可能有连续相同数字，注意处理就好

当 $a[i]\times 2 > m$ ，寻找到的第一个满足冲突的 $x$ ，必定满足不大于 $a[i]$ ，如果是等于 $a[i]$ ，会是相同值的第一个元素，此时计算右边多扣了一次 $a[i]$ ，加回去

当 $a[i]\times 2<m$ ，寻找到的第一个满足冲突的 $x$ ，一定大于 $a[i]$ ，在计算左边时会多计算一次自身，减回去

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
typedef long long ll;
using namespace std;
const int N=2e5+7;
const int M=998244353;
int n,m;
struct node{
    int idx,val;
}a[N];
ll s[N],ans[N];
bool cmp(node& a,node & b){
    return a.val<b.val;
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].val;
        a[i].idx=i;
        ans[i]=0;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        s[i]=s[i-1]+a[i].val;
    }
    for(int i=1;i<=n;i++){
        int l=1,r=n;
        while(l<r){
            int mid=(l+r)>>1;
            if(a[mid].val+a[i].val>m)r=mid;
            else l=mid+1;
        }
        int idx=a[i].idx;
        if(a[l].val+a[i].val > m){
            ans[idx]+=1LL*(l-1)*a[i].val;
            ans[idx]-=1LL*s[n]-s[l-1];
            if(a[i].val * 2 > m) ans[idx]+=a[i].val;
            else ans[idx]-=a[i].val;
        }
        else{
            ans[idx]+=1LL*(n-1)*a[i].val;
        }
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
    cout<<"\n";
    return;
}
int main(){
    IOS;
    int T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}