다다스와 쿼리

$A_0=U_0=V_0=0$으로 둔다. 위치 $i$를 덮고 있는 크기 $1$의 시행 수를 $U_i$, 크기 $X$의 시행 수를 $V_i$라고 하자. 그러면

$$U_i+XV_i=A_i$$

이며 $U_i,V_i$는 음이 아닌 정수이다.

고정된 두 수열 $U,V$를 만드는 데 필요한 시행 수는

$$\sum_{i=1}^{N}\max(0,U_i-U_{i-1})+\sum_{i=1}^{N}\max(0,V_i-V_{i-1})$$

이다. 증가한 만큼 새 구간을 시작하고, 감소한 만큼 기존 구간을 끝내면 이 값을 달성할 수 있다.

$F_i(c)$를 $1$번부터 $i$번 위치까지 만들었고 $V_i=c$일 때의 최소 비용이라고 하자. $\Delta_i=A_i-A_{i-1}$이고 이전 상태가 $d$라면 $e=c-d$에 대한 전이 비용은

$$h_{\Delta_i}(e)=\max(0,\Delta_i-Xe)+\max(0,e)$$

이다. 또한 $0\le c\le\lfloor A_i/X\rfloor$이어야 한다. 따라서 $F_i$는 정수 이산 볼록 함수이다.

정수 이산 볼록 함수 $f$의 켤레 함수를

$$f^*(s)=\max_z(sz-f(z))$$

로 정의한다. $1\le j\le X+1$에 대해

$$D_j(f)=f^*(-X+j)-f^*(-X+j-1)$$

로 둔다. $D_j(f)$는 기울기 $-X+j$에서의 가장 작은 최적 위치이다.

다음 성질을 사용한다.

• infimal convolution에서는 켤레 함수가 더해진다. 따라서 $D_j$도 더해진다.
• 함수의 정의역을 정수 구간 $[0,q]$로 제한하면 $D_j$는 $\operatorname{clamp}(D_j,0,q)$가 된다.
• $h_\Delta^*(-X)=-\Delta$이다.

$\Delta=Xq+r$ ($0\le r<X$)로 둔다. $d_j(\Delta)=D_j(h_\Delta)$는 다음과 같다.

$\Delta\ge0$이면

$$d_1=0,\qquad d_j=q+[r\ge X-j+2]\quad(2\le j\le X+1).$$

$\Delta<0$이면

$$d_j=q+[r\ge X-j+1]\quad(1\le j\le X),\qquad d_{X+1}=0.$$

여기서 대괄호는 조건이 참이면 $1$, 거짓이면 $0$이다. 이 식은 $h_\Delta(e)-(-X+j)e$의 이산 기울기를 조사하여 얻을 수 있다.

$z_j=D_j(F_{i-1})+d_j(\Delta_i)$라고 하자. $q_i=\lfloor A_i/X\rfloor$일 때

$$D_j(F_i)=\operatorname{clamp}(z_j,0,q_i)$$

이다. 또한 $\alpha_i=F_i^*(-X)$라 두면

$$\alpha_i=\alpha_{i-1}-\Delta_i+\sum_{j=1}^{X+1}\min(z_j,0)$$

이다.

항상 $D_1(F_i)=0$, $D_{X+1}(F_i)=q_i$이며 $j=X+1$ 상태가 $\alpha$에 더하는 값은 항상 $0$이다. 따라서 $j=2,3,\cdots,X$의 $X-1$개 상태만 저장하면 된다. $j=1$ 상태가 $\alpha$에 더하는 값은 각 위치의 상수항에 합칠 수 있다.

이제 하나의 상태 $j$를 고정하자. 한 위치는 입력 상태 $x$를

$$y=\operatorname{clamp}(x+d,0,q)$$

로 바꾸고, $\alpha$에 $\min(x+d,0)$을 더한다.

연속한 구간의 효과는 다음 다섯 정수로 표현할 수 있다.

$$y=\operatorname{clamp}(x+a,l,r),\qquad t=\min(x+p,c).$$

여기서 $t$는 이 구간이 $\alpha$에 더하는 값이다. 한 위치의 요약은

$$(a,l,r,p,c)=(d,0,q,d,0)$$

이다.

왼쪽 요약을 $(a_1,l_1,r_1,p_1,c_1)$, 오른쪽 요약을 $(a_2,l_2,r_2,p_2,c_2)$라고 하자. 왼쪽 다음에 오른쪽을 적용한 요약은

$$\begin{align*} a&=a_1+a_2,\\ l&=\operatorname{clamp}(l_1+a_2,l_2,r_2),\\ r&=\operatorname{clamp}(r_1+a_2,l_2,r_2),\\ p&=p_1+\min(l_1+p_2,c_2),\\ c&=c_1+\min(r_1+p_2,c_2) \end{align*}$$

이다. 각 상태를 독립적으로 합칠 수 있으므로 세그먼트 트리 노드의 병합에는 $O(X)$의 시간이 든다.

루트에서 입력 상태는 모두 $0$이다. 각 상태의 최종값은 $\operatorname{clamp}(a,l,r)$이고, $\alpha$에 더해지는 값은 $\min(p,c)$이다. 마지막으로

$$\min_c F_N(c)=-F_N^*(0)=-\left(\alpha_N+\sum_{j=2}^{X}D_j(F_N)\right)$$

를 출력한다.

모든 쿼리를 먼저 읽는다. 쿼리에서 한 번이라도 갱신되는 위치를 $p$라고 하면 바뀔 수 있는 전이는 $p$번과 $p+1$번뿐이다. 이 전이들의 위치 집합을 $S$라고 하자. $|S|\le2Q$이다.

$S$에 속하지 않는 위치는 모든 쿼리 동안 변하지 않는다. 이러한 위치의 각 최대 연속 구간을 처음에 하나의 요약으로 합친다. $S$의 각 위치는 길이 $1$인 요약으로 둔다. 이렇게 만든 압축 수열의 길이를 $K$라고 하면

$$K\le2|S|+1\le4Q+1$$

이다. 압축 수열 위에 세그먼트 트리를 만든다. 한 번의 업데이트에서는 $p$번과 $p+1$번에 대응하는 압축 리프만 다시 만든다.

전처리 시간 복잡도는 $O(X(N+Q)+Q\log Q)$이고, 쿼리당 시간 복잡도는 $O(X\log Q)$이다. 메모리 복잡도는 $O(N+Q+XQ)$이다.

Solution written by GPT5