バブルソートのswap回数
code:bubble.rb
cnt = 0
n.times do |i|
(i...n).each do |j|
cnt+=1
end
end
end
$ 0 \le a[i] \le 10^5 くらい
上みたいなのを実行したあとのcntの値
dat[x]：xを見た回数 を用意する（長さmax(ai)くらい、初期値0）
数列を前から見る
いまi番目を見ているとして、a[i] がswapされる回数 = i - sum(dat[0, a[i]))
a[0, i) が全部a[i]より大きかったら a[i] はi回swapされるけど、実際は違うので調整
見終わったら dat[a[i]]++
TODO: 分割統治で数え上げる