atcoder.jp
問題
- 長さ$N$の数列$A$が与えられるよ
- Q個のクエリを順番に処理してね
- クエリ1：$A$の中の要素$x$の直後に$y$を挿入してね
- クエリ2：$A$の中にある要素$x$を削除してね
- 全部のクエリを捌いた後の$A$はどうなってる？
成約
- $1 \leq N \leq 2 \times 10^{5}$
- $1 \leq Q \leq 2 \times 10^{5}$
- $A$の中の要素は常にユニーク
- クエリが与えられた時、$A$の中に$x$は絶対存在するよ
思考
- 電車の類題(ABC225D)を思い出す
- 特定の要素の、「前の数字は何？」と、「後ろの数字は何？」を管理・更新していくと良さそう
- クエリ1の捌き方：
- 「$x$の後ろの数字」をメモ(tmp)
- 「$y$の前の数字」を$x$に更新(新規作成)
- 「$y$の後ろの数字」を「$x$の後ろだった数字(tmp)」に更新（新規作成）
- 「$x$の後ろの数字」を$y$に更新
- 「$x$の後ろだった数字(tmp)の、前の数字」を、$y$に更新
- クエリ2の捌き方：
- 「$x$の後ろの数字」を、「$x$の後ろの後ろの数字」に更新
- 「$x$の前の前の数字」を、$x$に更新
- 本番は$N=1$のケースでめっちゃしばかれました(5ペナ)
- tips: 番兵として、先頭と末尾の車両を固定で置いておくと幸せになれました
コード
N = int(input())
A_L = [0] + list(map(int, input().split())) + [-1]
link_d = dict()
for i in range(1, N + 1):
link_d[A_L[i]] = [A_L[i - 1], A_L[i + 1]]
link_d[0] = [None, A_L[1]]
link_d[-1] = [A_L[N], None]
Q = int(input())
for _ in range(Q):
query = list(map(int, input().split()))
if query[0] == 1:
prev_num, add_num = query[1:]
next_num = link_d[prev_num][1]
link_d[prev_num][1] = add_num
link_d[add_num] = [prev_num, next_num]
link_d[next_num][0] = add_num
else:
del_num = query[1]
prev_num, next_num = link_d[del_num]
link_d[prev_num][1] = next_num
link_d[next_num][0] = prev_num
ans_L = []
now_num = 0
while True:
ans_L.append(now_num)
if link_d[now_num][1] == -1:
break
now_num = link_d[now_num][1]
print(*ans_L[1:])
