H - 桁差の和 (第13回 アルゴリズム実技検定) 別解（ソート・二分探索・累積和）

• 問題 https://atcoder.jp/contests/past202212-open/tasks/past202212_h
• 公式解説と違う解法なので書いておく
• Aはソートしてもいい
• Aiより数字が大きい箇所と小さい箇所、それは二分探索で分かる
• 範囲で和を求める箇所は累積和を使う
• 提出 https://atcoder.jp/contests/past202212-open/submissions/42777141

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    // input
    ll N;
    cin>>N;
    string s;cin>>s;
 
    VI A;
    rep(i, N){
      ll a = s[i] - '0';
      A.push_back(a);
    }
    SORT(A);
 
    AccSum Acc(A);
 
    ll sum=0;
    for(ll a : A){
      auto it = lower_bound(ALL(A), a);
      ll i = it - A.begin();
      
      // aの方が小さい部分
      {
        ll num = A.end() - it;
        sum += Acc.sum(i, N) - num*a;
      }
 
      // aの方が大きい部分
      {
        sum += a*i;
        sum -= Acc.sum(0,i);
      }
    }
    p(sum/2);
    
    return 0;
}