스케이트 연습과 쿼리

연습 구간이 $[L,R]$라고 하자. $R+1$번 지점에서는 속력이 $0$이어야 하므로, 오른쪽에서 왼쪽으로 최적 속력을 정하면 된다. $s_{R+1}=0$으로 두면

$s_i=\min(V_i,s_{i+1}+1)$

이 항상 최적이다. 속력은 왼쪽에서 오른쪽으로 증가할 때 제한이 없으므로, 각 위치에서는 오른쪽으로 무사히 내려갈 수 있는 최대 속력을 잡으면 된다.

이제 오른쪽 끝 $R$을 $1$부터 $N$까지 증가시키며 모든 질의를 오프라인으로 처리한다. 현재 오른쪽 끝이 $R$일 때, $s_i=V_i$인 가장 오른쪽 위치를 last라고 하자. last보다 오른쪽의 모든 위치는 속도 제한에 걸리지 않고 도착점 때문에만 제한되므로, $i>\text{last}$에 대해 $s_i=R+1-i$이다.

오른쪽 끝을 $R-1$에서 $R$로 늘릴 때, 이전 last를 기준으로 다음 변화가 생긴다.

• $L>\text{last}$인 시작점의 답은 $R-L+1$만큼 증가한다.
• $L\le \text{last}$인 시작점의 답은 $R-\text{last}$만큼 증가한다.

또한 새로 속도 제한에 걸리는 위치는 정확히 $i+V_i=R+1$을 만족하는 위치들이다. 따라서 각 값 $i+V_i$에 대해 가장 큰 $i$만 저장해 두면, last는 전체 과정에서 단조 증가한다.

각 시작점 $L$에 대해 last가 처음으로 $L$ 이상이 되는 시각을 $B_L$이라고 하자. last가 한 번 증가할 때 지나가는 $L$들에 대해 $B_L$을 채우면 전체 $O(N)$이다.

또 $P_R=\sum_{t=1}^{R}(t-\text{last}_{t-1})$를 전처리한다. 그러면 질의 $[L,R]$의 답은 다음과 같다.

• $R\le B_L$이면 답은 $1+2+\cdots+(R-L+1)$이다.
• $R>B_L$이면 답은 $1+2+\cdots+(B_L-L+1)+P_R-P_{B_L}$이다.

따라서 전체 시간 복잡도는 $O(N+Q)$, 메모리 복잡도는 $O(N+Q)$이다.