h_chiro https://blog.hatena.ne.jp/h_chiro/ 雑記 https://h-chiro.hatenablog.com/ PKU http://poj.org/problem?id=2299 概要 バブルソートする際にswapする回数を求める。 数列の長さが500000以下なので、実際にバブルソートすると間に合わない。 マージソートを行いながら、この数をもとめることが可能で数列の逆転数は、左半分の逆転数、右半分の逆転数、右半分の各要素に対して自身より大きい要素がいくつあるかの和で求めることができる。 ソース #include<cstdio> #include<vector> #include<cassert> #include<algorithm> using namespace std; #define REP(i,a… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fh-chiro.hatenablog.com%2Fentry%2F20101109%2F1289257350" title=" 2299 Ultra-QuickSort - 雑記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2010-11-09 08:02:30 rich https://h-chiro.hatenablog.com/entry/20101109/1289257350 1.0 100%