CF 893Div2E2. Rollback (Hard version) / Persistent 자료 구조

문제: https://codeforces.com/contest/1858/problem/E2

 

자료구조의 Persistency를 관리하는 문제다. 자료구조의 Persistency는 주로 다음과 같은 문제이다.

 

• 어떤 자료구조 $S$를 구현하여라.
• $S$의 가장 마지막으로 진행한 연산을 취소해라.

이런 문제는 대개 다음과 같은 방법으로 풀린다.

1. $S$를 구현한다. 단, $S$에서는 "amortization"을 쓸 수 없다.
2. $S$에 어떤 연산을 진행할 때, $S$의 변경 기록을 저장한다.
3. $S$의 마지막 연산을 취소할 때, 변경 기록을 역으로 돌린다.

 

무슨 말인지 살펴보자.

• "amortization"을 쓸 수 없다.
  • 우리가 쓰는 자료구조 중에서는, 각 연산은 오래 걸릴 수 있지만, 전체 연산의 시간 복잡도는 특정 시간 이내로 bound되는 형태가 있다. 이를 amortization이라고 한다. 가령이면, $N$번의 연산을 하는데 한 번은 $N$, 나머지는 전부다 $1$의 시간이 들면 전체 시간은 $O(N)$이고, (연산당) amortized $O(1)$ 시간이 든다고 한다.
  • 이런 연산들은 rollback을 하기에 적절하지 않다. 예를 들면, 동적할당을 하는 std::vector가 그렇다. 가령이면, 동적 배열을 잡지 못하고 미리 최대 크기의 배열을 잡아놓아야 한다.
  • 요점은 "메모리의 변경"이 특정 횟수 $T$이내에 bound되어야 한다.
• $S$의 변경 기록을 저장한다.
  • 보통 자료구조는 "되돌리기" 기능이 없다. 보통, $a[x] = p$와 같은 연산이 되돌릴 수 없어서 그렇다. (덮어쓰면, 원래 값이 뭐였는지 알 수 없다.) 하지만 우리가 명시적으로, "$a$의 $x$번째 원소가 $a[x]$에서 $p$로 바뀌었다." 와 같은 정보를 저장하면 해당 연산을 복구할 수 있다.
  • $S$에 어떤 연산을 해서 메모리의 변경이 이루어졌다면, 스택을 이용해서 해당 변경을 저장한다. 어떤 메모리의 어떤 수가 어디서 어디로 바뀌었는지 저장하면, 이 연산을 Undo해서 원래대로 돌려줄 수 있다. 메모리의 변경 횟수는 $T$회 이내이므로, 해당 변경은 $T$ 이내의 메모리로 저장될 수 있다.
  • 변경은 "가장 마지막에 한 행동"이 취소되므로, Stack에 저장한다.
• $S$의 변경 기록을 역으로 돌린다.
  • 마지막 연산에서 사용한 변경들이 $T$개 이내로 있을 것이다. 해당 $T$개의 연산들을 전부다 rollback한다.
    • 연산의 경계가 어디인지 잘 저장하고 있어야 한다. stack에 연산 단위로 stack을 묶어서 활용하는 것이 도움이 된다.

이제 임의의 amortization없이 구현된 $S$라는 자료구조에 roll-back을 추가할 수 있다!

 

근데 버추얼때 문제 못푼거는 그냥 이 위에거 다 알고 있는데 $S$를 어떻게 amortization없이 구현할 수 있는지를 모르겠어서 그렇다... 그냥 반성하자.

이 문제의 경우에는, 배열 $a$의 내용, 배열 $a$의 크기, $a$에서 $v$가 가장 처음 등장한 위치, 배열 $a$의 $i$번째 원소가 가장 처음으로 등장하는 $v=a[i]$인지를 저장하면 된다.

• 배열 $a$에서 $k$개의 수를 삭제하는건 그냥 배열 $a$의 크기를 줄이면 된다.
• 배열 $a$에서 수를 추가하는 건, $a$의 내용과 크기는 추가하면 되는데, $a$에서 $v$가 가장 처음 등장한 위치를 저장할 때는 정말로 조심해야한다. $a$에서 $v$가 가장 처음 등장한 위치를 저장할 때, 이를 잘 update 해줘야한다. (현재 배열 $a$의 크기를 넘어가는 경우 invalid하다고 처리해서 잘 reset하면 된다)

참고로 std::stack은 쓰지 말자, deque 기반이라서 메모리 초과난다.

 

지금 봤으면 더 봤을 수 있을 것 같은데 흑흑 (코드는 $T = 6$이다)

https://codeforces.com/contest/1858/submission/220810643