AGC 003 C - BBuBBBlesort!

• 問題

問題概要

数列{a_i} (1 <= i <= N)が与えられる.
1. 連続する2数を入れ替える
2. 連続する3数を反転させる
の2つの操作を行い単調増加数列にする時,1.の最小回数を求めよ.
1 <= N <= 10⁵ , i != j => a[i] != a[j]

解法

2.では奇数番目/偶数番目の数の順番を任意の場所に入れ替えることができる.
また,1.は連続する2数の偶奇を入れ替えることができる.
{a_i}で奇数番目であり,{a_i}をソートした{b_i}で偶数番目の数(1)の個数をXとする.
これは{a_i}で偶数番目かつ{b_i}で奇数番目(2)の数の個数と等しい.
そのような数が存在する時,(1)と(2)が隣り合うように2.の操作で動かし,
1.でその2数を入れ替えるという操作をX回繰り返すと,そのような数をなくすことができる.
あとは2.で偶奇に関してソートすれば単調増加数列にできる.
また,自明に(1),(2)のような数が隣り合うことはないので最低X回は1.が必要なため,
Xが答えとなる.

メモ

偶奇に関してソートできることはわかったが,(*1)が隣り合っていたら無理じゃんとなった.
入れ替える(またはそれを先頭に持ってくる)という発想がなかった.惜しい.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60;
const int MAX_N = 100005;

int a[MAX_N],b[MAX_N];

int main(){
  int N; cin >> N;
  rep(i,N) scanf("%d",a+i);
  copy(a,a+N,b);
  sort(b,b+N);
  int ans = 0;
  rep(i,N){
    int ind = int(lower_bound(b,b+N,a[i])-b);
    if(i%2==0 && ind%2==1) ans++;
  }
  cout << ans << endl;
  return 0;
}