슬라이딩 윈도우 RMQ

길이 $N$의 수열 $A_1,A_2,\ldots,A_N$과 정수 $K$가 주어진다. 각 $i=K,K+1,\ldots,N$에 대하여 연속한 $K$개 원소 $A_{i-K+1},\ldots,A_i$의 최솟값을 구한다.

수열을 입력으로 직접 주지 않고 아래의 점화식으로 생성한다. 모든 $i\geq1$에 대해

이다. $A_0,a,c,m$은 입력으로 주어진다.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 케이스마다 $B_i=\min(A_{i-K+1},\ldots,A_i)$ ()라고 할 때, 을 한 줄에 출력한다. 는 비트 단위 XOR 연산이다.

• $1\leq T\leq100\,000$.
• $1\leq K\leq10^6$.