筆者はレート800前後の茶～緑コーダ
ABC470のD問題を解いていく
実装コード
置換 A とその逆置換 B を同時に管理し、2種類のクエリを高速に処理する。
-
N,Qと置換Aを0-indexedで受け取る -
B[A[i]] = iとして、Aの逆置換Bを作る - クエリ1では、指定された位置
x,yの値をA上で交換する -
Aの交換後にB[A[x]]とB[A[y]]も交換し、逆置換の対応を保つ - クエリ2では
AとBを入れ替え、現在の置換をその逆置換にする - すべてのクエリを処理したら、
Aの各値を1-indexedに戻して出力する
main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def rI1(): return int(sys.stdin.readline().rstrip()) - 1
def rLI1(): return list(map(lambda a: int(a) - 1, sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0")) == 0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)
def main():
N, Q = rLI()
A = rLI1()
B = [0] * N
for i, a in enumerate(A):
B[a] = i
for _ in range(Q):
query = rLI()
if query[0] == 1:
x, y = query[1] - 1, query[2] - 1
A[x], A[y] = A[y], A[x]
B[A[x]], B[A[y]] = B[A[y]], B[A[x]]
else:
A, B = B, A
print(*[a + 1 for a in A])
if __name__ == '__main__':
main()
感想
解説の置換と逆置換を両方持つことで、要素の交換後も対応関係を簡単に更新できるのが勉強になった。
A と B の入れ替えだけで逆置換のクエリを処理できるのは覚えておきたい。