ボゾソート [パソコン甲子園2018 予選 F]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0385

考察過程

1. 愚直にシミュレートして行けば良さそう
2. そのためには昇順になったかを高速に判定する必要がある
3. Aを昇順にしたものと同じ場所になった個数を数えればいい？
4. 同じ場所になった個数がN個になったら、ソート完了
5. これは差分だけ計算し直すことができる

解法

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0385/judge/3162168/C++14

ソート済みの配列Aを配列Bとする。
「cnt := A[i]=B[i]である要素数」として、これを更新しながら、ソートされたかを確認する。
cntを計算し、もう既にNであれば、0を返して終了。
　
x,yをスワップするが、スワップ前にcntを更新する。
スワップ後にcntを更新する。
このように差分計算をするときは、現在の状態を打ち消して、処理をして、計算し直すという手順をとる。

int N, A[301010], B[301010], Q;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    cin >> Q;

    rep(i, 0, N) B[i] = A[i];
    sort(B, B + N);

    int cnt = 0;
    rep(i, 0, N) if (A[i] == B[i]) cnt++;

    if (cnt == N) {
        printf("0\n");
        return;
    }

    rep(q, 0, Q) {
        int x, y; cin >> x >> y;
        x--; y--;

        if (A[x] == B[x]) cnt--;
        if (A[y] == B[y]) cnt--;

        swap(A[x], A[y]);

        if (A[x] == B[x]) cnt++;
        if (A[y] == B[y]) cnt++;

        if (cnt == N) {
            printf("%d\n", q + 1);
            return;
        }
    }

    printf("-1\n");
}