Eau de Cologne
CF 893Div2E2. Rollback (Hard version) / Persistent 자료 구조
문제: https://codeforces.com/contest/1858/problem/E2 자료구조의 Persistency를 관리하는 문제다. 자료구조의 Persistency는 주로 다음과 같은 문제이다. 어떤 자료구조 $S$를 구현하여라. $S$의 가장 마지막으로 진행한 연산을 취소해라. 이런 문제는 대개 다음과 같은 방법으로 풀린다. $S$를 구현한다. 단, $S$에서는 "amortization"을 쓸 수 없다. $S$에 어떤 연산을 진행할 때, $S$의 변경 기록을 저장한다. $S$의 마지막 연산을 취소할 때, 변경 기록을 역으로 돌린다. 무슨 말인지 살펴보자. "amortization"을 쓸 수 없다. 우리가 쓰는 자료구조 중에서는, 각 연산은 오래 걸릴 수 있지만, 전체 연산의 시간 복잡도는 특..
codeforces
2023. 8. 28. 13:50