D-ABS SUM（技術室奥プログラミングコンテスト#6 Day1）

• Quiz
  • https://atcoder.jp/contests/tkppc6-1/tasks/tkppc6_1_d
• AC
  • https://atcoder.jp/contests/tkppc6-1/submissions/25307869
• 解説
  • 区間を累積和で書き直す
  • 累積和を各項Biとした配列Bをソートして、i, j (i<j) の全組み合わせについてBj - Biの和を取れば答え
• 以下の画像はN=4の場合

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;
    cin>>N;

    VI A(N);
    rep(i, N){
      cin >> A[i];
    }

    VI B(N+1);
    rep(i,N){
      B[i+1] = A[i];
    }
    rep(i,N){
      B[i+1] += B[i];
    }
    SORT(B);

    mint sum=0;
    FOR(i,1,N+1){
      sum += i*(B[i]%mod); // mod必要！(overflow)
    }
    rep(i,N){
      sum -= (B[i]%mod)*(N-i); // mod必要！(overflow)
    }
    p(sum.x);
    
    return 0;
}