差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:dynamic_programming:inversion [2018/05/28] – ikatakos | programming_algorithm:dynamic_programming:inversion [2018/09/24] – [転倒数] ikatakos | ||
---|---|---|---|
行 12: | 行 12: | ||
3 10 | 3 10 | ||
+ | × | ||
3 | 3 | ||
+ | × | ||
3 | 3 | ||
+ | × | ||
3 | 3 | ||
+ | × | ||
1 | 1 | ||
+ | × | ||
1 | 1 | ||
行 65: | 行 70: | ||
先頭から順番に処理しているので、今BITにあるのは「自分より左に各数がいくつあるか」の情報である。 | 先頭から順番に処理しているので、今BITにあるのは「自分より左に各数がいくつあるか」の情報である。 | ||
- | 自分より左で $p_i$ より小さい数の個数は、$SUM(p_i)$(BITで $1$~$p_i$ の和)を求めることで得られる。 | + | 自分より左で $p_i$ 以下の数の個数は、$SUM(p_i)$(BITで $1$~$p_i$ の和)を求めることで得られる。 |
逆に言うと、$p_i$ より大きい数の個数は、$i - SUM(p_i)$ である。 | 逆に言うと、$p_i$ より大きい数の個数は、$i - SUM(p_i)$ である。 |