题解 · 457

题解

$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$ 일 때의 최소 비용이라고 하자. 이고 이전 상태가 라면 에 대한 전이 비용은

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$ 에서의 가장 작은 최적 위치이다.

다음 성질을 사용한다.

$\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)$ 라고 하자. 일 때

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$ 를

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)$ , 오른쪽 요약을 라고 하자. 왼쪽 다음에 오른쪽을 적용한 요약은

\begin{aligned} a & = a_{1} + a_{2}, \\ l & = clamp (l_{1} + a_{2}, l_{2}, r_{2}), \\ r & = clamp (r_{1} + a_{2}, l_{2}, r_{2}), \\ p & = p_{1} + \min (l_{1} + p_{2}, c_{2}), \\ c & =_{} \end{aligned}

이다. 각 상태를 독립적으로 합칠 수 있으므로 세그먼트 트리 노드의 병합에는 $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)$ 이다. 메모리 복잡도는 이다.

Solution written by GPT5