2299 Ultra-QuickSort

http://poj.org/problem?id=2299

概要

バブルソートする際にswapする回数を求める。
数列の長さが500000以下なので、実際にバブルソートすると間に合わない。
マージソートを行いながら、この数をもとめることが可能で数列の逆転数は、左半分の逆転数、右半分の逆転数、右半分の各要素に対して自身より大きい要素がいくつあるかの和で求めることができる。

ソース

#include<cstdio>
#include<vector>
#include<cassert>
#include<algorithm>
using namespace std;

#define REP(i,a,b) for(int i=a; i<b; ++i)

void merge(int start, int end, vector<int> &v) {
  vector<int> tmp = vector<int>(v.begin()+start, v.begin()+end+1);
  sort(tmp.begin(), tmp.end());
  REP(i,start,end+1) v[i] = tmp[i-start];
  return;
}

long long rec(int start,int end,vector<int> &v) {
  assert(start<=end);

  if(end == start) return 0;
  if(end - start == 1) {
    if(v[start] > v[end]) {
      swap(v[start],v[start+1]);
      return 1;
    }else return 0;
  }

  int mid = (start+end)/2;
  long long ret = rec(start,mid,v) + rec(mid+1,end,v);

  vector<int>::iterator it1 = v.begin()+start, it2 = v.begin()+mid+1;
  REP(i,mid+1,end+1) ret += distance(lower_bound(it1, it2, v[i]), it2);
  merge(start,end,v);

  return ret;
}

int main() {
  int n;
  while(scanf("%d", &n), n) {
    vector<int> v = vector<int>(n);
    REP(i,0,n) scanf("%d",&(v[i]));
    printf("%lld\n", rec(0,v.size()-1,v));
  }
}