슬라이딩 윈도우 RMQ

서브태스크 $1$에서는 수열을 생성한 뒤 모든 길이 $K$ 구간을 직접 훑을 수 있다. 서브태스크 $2$에서는 크기 $K$의 순환 배열에 새 값을 덮어쓰고 구간 최솟값 세그먼트 트리의 루트 값을 읽으면 된다.

전체 문제에서는 후보 원소의 인덱스를 덱에 저장한다. 맨 앞 원소가 현재 구간에서 벗어나면 제거한다. 새 값 $A_i$를 넣기 전에 덱 뒤에서 $A_i$ 이상인 값들을 모두 제거한다. 새 값을 뒤에 넣으면 덱의 값은 앞에서 뒤로 엄격히 증가하고, 맨 앞이 현재 구간의 최솟값이 된다. 제거된 값은 나중의 어느 구간에서도 새 값보다 유리할 수 없으므로 정답에 영향을 주지 않는다. 각 원소는 덱에 한 번 들어가고 한 번 이하 제거되므로 총 $O(N)$ 시간과 $O(K)$ 공간을 사용한다.

$A_0$ 자체는 구간에 포함되지 않는다. 곱셈 $aA_{i-1}+c$는 32비트 범위를 넘으므로 64비트 정수로 계산한다.

Solution written by GPT6