ピボット (Pivots) [Aizu Competitive Programming Camp 2018 Day 3 B]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day3/problems/B

前提知識

• 双方向リスト

考察過程

1. 全然分からない
2. 参加記でリストという単語を発見
3. なるほどー
4. 双方向リスト作るんね

実装

https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC2018Day3/3149978

双方向リストを作ろう。
クエリの処理は最高でも5つのノードを変更するだけで実現できる。
N=1のときはノードが1つになり、バグりそうな雰囲気を感じたので場合分けしてある。
あとは、実装する。
　
L[i] := ノードiの左側にあるノード
R[i] := ノードiの右側にあるノード
top := リストの先頭ノード
last := リストの末尾ノード

を用意して、適宜切り貼りしていく。
プログラムにコメントをつけたので追ってみるといいが、双方向リストを直接学んだ方が早いかもしれない。

int N, Q, A[101010];
int L[101010], R[101010];
int top, last;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) A[i]--;

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

    top = A[0];
    last = A[N - 1];
    rep(i, 0, N) {
        if (i) L[A[i]] = A[i - 1];
        else L[A[i]] = -1;

        if (i + 1 < N) R[A[i]] = A[i + 1];
        else R[A[i]] = -1;
    }

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

        if (q == top) { // qが先頭だったとき
            top = R[q]; // qの右側が先頭になる
            L[top] = -1; // 先頭の左側はなくなる
            R[last] = q; // 末尾にqが来るので、現在の末尾の右側はq
            L[q] = last; // qの左側は現在の末尾
            R[q] = -1; // qは末尾になるので、右側はなくなる
            last = q; // 末尾がqであることをメモ
        }
        else if (q == last) { // qが末尾だったとき
            last = L[q]; // qの左側が末尾に成る
            R[last] = -1; // 末尾の右側はなくなる
            L[top] = q; // 先頭にqが来るので、現在の先頭の左側はq
            R[q] = top; // qの右側は先頭になる
            L[q] = -1; // qの左側はなくなる
            top = q; // 先頭がqであることをメモ
        } else {
            int nxtop = R[q]; // qの右側が次の先頭になる
            int nxlast = L[q]; // qの左側が次の末尾になる

            L[q] = last; // qの右側を現在の末尾にする
            R[q] = top; // qの左側を現在の先頭にする

            L[nxtop] = -1; // 次の先頭の左側はなくなる
            R[nxlast] = -1; // 次の末尾の右側はなくなる

            L[top] = q; // 今の先頭の左側はqになる
            R[last] = q; // 今の末尾の右側はqになる

            top = nxtop; // 先頭更新
            last = nxlast; // 末尾更新
        }
    }

    int f = 1;
    rep(i, 0, N) if (L[i] < 0) top = i;
    while (0 <= top) {
        if (f) f = 0;
        else printf(" ");

        printf("%d", top + 1);
        top = R[top];
    }
    printf("\n");
}