公式解説の補足です。

オリジナル問題の想定解法について

slope trick としてよく知られているデータ構造を用いて解説と同じように解くことができます。下の maspy さんの記事がよくまとめられていると思います。

https://maspypy.com/slope-trick-1-解説編

これを知っていると、答えに対する寄与が簡単に理解できると思います。

この問題の解法について

主客転倒として知られているテクニックがあります。

\(0\) 以上 \(M\) 未満の非負整数列 \((A_{1}, A_{2},\dots,A_{M})\) があります。任意の整数 \(1\leq i\leq M\) に対して、 \(i\) 以上の要素の個数を \(C_{i}\) とします。このとき、\(\sum A = \sum C\) が成り立ちます。

これを用いて計算することもできます。

つまり、任意の正整数 \(x\) に対して、\(ans\) から引かれる数のうち \(x\) 以上のものが何個あるかが分かれば良いです。これは、 \(S\) に含まれる \(x\) 未満の数を管理することで求めることができます。詳しくは実装例をご覧ください。

c++ による実装例