AGC003 C - BBuBBBlesort!

問題

長さnの数列が与えられる
これを以下の操作を繰り返して単調増加に並べたい
操作1) 連続する2要素を選び反転する
操作2) 連続する3要素を選び反転する
後者は何度でもしていいとき、前者を最小で何回行う必要があるか求める

1 <= n <= 10^5

解法

まず操作2だけでソートできないのはどういう場合か考える
操作2は「要素iと要素i+2をswapする」と言い換えられる
つまり操作2によって各要素のインデックスの偶奇は変わらない
ということは、最終的に左から偶数番目の位置にないといけない要素が初期状態で左から奇数番目にあった場合、その要素のために必ず操作1が必要になる
そういう要素がk個あるとすると、それらに対応する「左から奇数番目の位置にないといけないのに初期状態で左から偶数番目の位置にある」要素も当然k個存在する
それら2k個の要素全ての偶奇を正すには操作1が最低k回は必要

条件の通り、「左から偶数番目にある要素同士」と「左から奇数番目にある要素同士」は全て操作2で自由に入れ替えられる
だから↑で言ったk個のペアをそれぞれ隣り合わせることももちろん可能で、そうしてから操作1をすれば2要素の偶奇を一気に正せる
これをk回繰り返せば全てのペアの偶奇が正せて、その後適当に操作2でソートすれば題意を満たせる

以上より結局kが答え
{要素の値、初期のインデックス}ってpairの配列をsortしてkを求めればいい

int n, res;
pair<int,int> p[100100];

signed main() {
	cin >> n;
	rep(i,n) {
		cin >> p[i].first;
		p[i].second = i;
	}
	sort(p,p+n);
	rep(i,n) if (p[i].second%2!=i%2) res++;
	cout << res/2 << endl;
}