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"); }
