第三回 アルゴリズム実技検定 (PAST) N - 入れ替えと並び替え

問題

解法

解説にもある通り、バブルソートを用いてソートすれば全体の計算量は O(Q * (1回の隣接swapにかかる計算量) ) に収まる。
swapはもちろん O(1) になるが、今回は候補を更新する & 次の候補を見つける必要がある。

swapごとに a[idx] > a[idx + 1] を満たす idx (これを転倒数と呼ぶ) を candsに入れ、満たさなくなったものは消していくことにすると、
cands に入ったり消えたりするような数は idx - 1, idx, idx + 1 のうちどれかになるのでこれらをチェックする。(update関数のところ)
このupdate操作を繰り返していけば区間を正しくソートすることができる。
どこをswapするかは [x[q], y[q]] から適当に選んでいけばいいが、今回はlower_boundを使っている。

全体の計算量は O(Q log N + N)。

コード

void solve(long long N, long long Q, std::vector<long long> t, std::vector<long long> x, std::vector<long long> y){
  set<Int> cands;
  vi a(N);
  iota(ALL(a), 1LL);
  auto update = [&](Int idx){
    swap(a[idx], a[idx + 1]);
    for(Int temp = idx - 1; temp <= idx + 1; temp++){
      if(temp < 0 || temp + 1 >= N) continue;
      if(a[temp] < a[temp + 1]) cands.erase(temp);
      else cands.insert(temp);
    }
  };
  rep(q, Q){
    x[q]--; y[q]--;
    if(t[q] == 1){
      update(x[q]);
      continue;
    }
    for(;;){
      auto itr = cands.lower_bound(x[q]);
      if(itr == cands.end() || *itr >= y[q]) break;
      // bubble sort
      update(*itr);
    }
  }
  rep(i, N) cout << a[i] << ( i == N-1 ? "\n" : " " );
}

template is here