27973번 - 지연 평가

지연이는 자신이 가진 배열 $S$의 상태를 평가하려고 한다. 처음에 $S$에는 $1$부터 $1 \, 234 \, 567 \, 890 \, 123$까지의 모든 정수가 $1$개씩 들어 있다.

지연이를 도와 다음 명령을 수행하는 프로그램을 작성하시오.

• 0 x: $S$의 모든 원소에 x를 더한다. $(-100 \, 000 \leq$ x $\leq 100 \, 000)$
• 1 x: $S$의 모든 원소에 x를 곱한다. $(1 \leq$ x $\leq 100)$
• 2 n: $S$에서 작은 원소부터 차례대로 n개를 제거한다. $(1 \leq$ n $\leq 100 \, 000 \, 000)$
• 3: $S$에서 가장 작은 원소를 출력한다.

이 문제의 풀이를 작성하기 전에, 예제 밑의 힌트를 참조할 수 있다.

첫 줄에 명령의 개수 $Q$가 주어진다. $(1 \leq Q \leq 170 \, 000)$

다음 줄부터 위에서 설명한 네 개의 명령 중 하나가 주어진다. x, n은 정수이다.

하나의 테스트케이스에서 2번 명령으로 들어오는 모든 n의 합은 $1 \, 234 \, 567 \, 890 \, 120$ 이하이다.

하나의 테스트케이스에서 배열 $S$에 들어 있는 어떤 수든지 그 절댓값이 언제나 $10^{18}$ 이하가 되도록 하는 명령만이 주어진다.

마지막 명령은 항상 3이다.

3번 명령이 들어올 때마다 그 시점에서 $S$에서 가장 작은 값을 한 줄에 하나씩 출력한다.

Python 사용자라면, 간단한 테스트로 다음 두 프로그램을 로컬에서 돌려 보자.

a = [0] * (10 ** 15) # 10**15 byte is 1 Petabyte
print("calculating done!")

a = range(10 ** 15)
print("calculating done!")

두 번째 프로그램은 바로 끝나지만, 첫 번째 프로그램은 메모리 에러가 발생하는 것을 알 수 있다. 이는 range(10 ** 15) 구문이 $0$부터 $10^{15} - 1$까지의 모든 수를 즉시 생성하는 구문이 아니기 때문이다! 대신, 이 객체는 일단 어딘가에 이 모든 수가 만들어져 있다고 가정하고, 필요할 때마다 수를 $0$, $1$, $2$, $3$, ... 순으로 만들어서 준다. 따라서 파이썬의 range 객체는 실제로는 start, stop, step이라는 단 3개의 정수만을 내부에 저장하고 있다. 이처럼 결과가 필요할 때까지 표현식의 평가를 미루어 두는 기법을 지연 평가(Lazy evaluation)라고 한다. 만약 실제로 $10^{15}$까지의 수가 모두 필요한 것이 아니라면(예를 들어, $100$번째 소수를 발견했을 때 for문을 멈추고 그 값을 리턴하고 싶다면), 지연 평가가 많은 도움이 된다. 마찬가지로 이 문제를 풀기 위해서 $1$부터 $1\,234\,567\,890\,123$까지의 모든 자연수를 하나씩 직접 생성한다면 시간과 메모리를 엄청나게 잡아먹을 것이다. 지연 평가를 사용해서 이 문제를 보다 효율적으로 풀 수 있는 방법을 찾아보자.