2020/06/25 - いろいろな記録

解説AC : 30分

おもろい。数字の位置をメモしておいて、降順に入れながらその数字が二番目となる領域を足していく。

各 $L,\,R$ に対して $X_{L,R}$ を求めていると $N^2$ 回見ることになって間に合わないので、 $P$ の各要素が何回全体に寄与するかを考えれば良い、という発想は典型っぽい。

実装はsetとその中でのにぶたんを使うと楽ですね。prevとnextというイテレータいじるやつ初めて知った。setもそれなりに慣れてきた。

自力AC : 20分

上の問題の下位互換。