Chokudai Speed Run J-転倒数

転倒数、競プロに慣れてないと難しいと思いませんか？僕は難しいと思います。

リンク

https://atcoder.jp/contests/chokudai_S001/tasks/chokudai_S001_j

f:id:ayaya09:20200102182445p:plain

問題は次のようにいいかえられる。

問題概要

自然数 $N$ と、 $1～N$ を並び替えた配列 $a[1]～a[N]$ が与えられる。
$0 \lt i \lt j \leqq N$ かつ $a[ i ] \gt a[ j ]$ を満たすような $(i,j)$ の組の数を求めよ。

方針・実装

各 $j$ について、 $(i,j)$ が条件を満たすような $i$ の数を数える。 $a[ i ] \gt a[ j ]$ であるから、 $j$ を大きいほうからみてうまく数えられないかなーとなる。

＊注意：説明では1-indexedにしていますが実際は0-indexedのほうがやりやすいと思います。

すでに見た数字がある要素の位置の集合を $S$ とするとき、次のようなことができればよい。( $k$ は $j$ の位置)

A. $S$ のうち $k$ より小さいものの数を求める。

B. $S$ に $k$ を挿入する。

そのために、セグ木を用いる。このデータ構造は、次のようなことが十分高速にできる。(正確には $O(logN)$ )

・ある要素に値を足す

・ある区間の和を求める

これを用いて

・ $[1,k]$ の要素の和を求める

・ $k$ 番目の要素に $1$ を足す

と、それぞれA,Bに対応する。

例

$eq.N=4,a[1]=2,a[2]=4,a[3]=3,a[4]=1$ の時の転倒数を求める。まず、大きい値から見た位置は $[2,3,1,4$ ]である。

$j=2$ になるような $(i,j)$ の組は、もちろん $0$ である( $a[j]はj=2$ で最大値をとるので)。

ここでセグ木の $2$ の位置に $1$ を加算する。セグ木の中身は、 $(0,1,0,0)$ となっている。「次に $j$ が位置 $k$ に入るときにあり得るような $i$ の数」は、セグ木の $[1,k]$ の区間の和で求められる。この場合、 $1$ の位置に $3$ が入れば答えは $0$ 増えるし、 $4$ の位置に入れば答えは $1$ 増える。この場合 $3$ は $3$ に入るので、 $j=3$ のときの $i$ の個数は $1$ であり、セグ木の $3$ の位置に1を足す。

セグ木の中身は $(0,1,1,0)$ となる。同様に、 $2$ は $1$ の位置に入るので $j=2$ のときの $i$ の個数は $0$ であり、セグ木の $1$ の位置に $1$ を足す。この時のセグ木の中身は $(1,1,1,0)$ となる。最後に $1$ は $4$ の位置に入るので $j=1$ のときの $i$ の個数は $3$ であり,セグ木の中身は $(1,1,1,1)$ となる。求める答えは $0+1+0+3=4$ となる。

コード

https://atcoder.jp/contests/chokudai_S001/submissions/9285044