덱 조작과 쿼리

시간 제한2초메모리 제한1024 MB

요약
덱에 push, pop, print, 그리고 이전 상태로 되돌리는 restore 연산을 처리하며, print마다 현재 카드 값의 합을 출력한다.
난이도

어려움10점 중 8점

유형
트리, 백트래킹, 누적 합, 구현
정답자
아직 제출이 없습니다

문제

하넬은 카드게임의 덱(deck)을 조작하는 방법을 연구하고 있다. 덱은 위와 아래가 있는 카드의 리스트고, 각 카드에는 00 이상 10910^9 이하의 정수가 하나씩 적혀있다. 덱은 처음에 카드가 없는 비어있는 상태고, 하넬은 현재 덱에 4가지 중 하나의 행동을 해서 덱의 상태를 바꾸고자 한다:

  • pushxx: xx가 적혀있는 카드를 덱의 가장 위에 둔다. (0≤x≤109)(0 \le x\le 10^9)
  • pop: 덱 가장 위에서 카드를 제거한다. 현재 덱에 카드가 없는 경우에는 pop이 주어지지 않는다.
  • restoreii: 현재 덱의 상태를 ii번째 행동 이후의 덱의 상태와 동일하게 만든다. ii가 00인 경우는 덱을 카드가 없는 초기 상태로 되돌린다. ii번째 행동이 아직 이뤄지지 않은 경우는 주어지지 않는다.
  • print: 현재 덱에 있는 카드에 적힌 모든 수의 합을 출력한다. 덱에 카드가 11장도 없을 경우에는 00을 출력한다.

하넬은 아쉽게도 덱 조작 방법을 연구하느라 바쁘다. 하넬을 대신해서 각 print행동이 주어질 때 덱에 있는 카드의 수를 계산해주자.

입력

첫 번째 줄에 행동의 수 NN가 주어진다. (1≤N≤500,000)(1\le N\le 500\\,000)

두 번째 줄 부터 NN개의 줄에 걸쳐 행동이 문제에 적힌 형식대로 한 줄에 하나씩 주어진다. push와 xx, restore와 ii사이에는 공백이 하나씩 주어지며, print 명령은 반드시 11개 이상 주어진다.

출력

print 행동이 주어질 때마다 덱에 있는 카드의 수의 합을 한 줄에 하나씩 출력한다.

예제2

  1. 예제 1

    입력
    5
print
push 10
push 20
pop
print
    예상 출력
    0
10

  2. 예제 2

    입력
    11
push 10
push 20
push 30
print
pop
pop
print
restore 3
pop
push 40
print
    예상 출력
    60
10
70