Dadas and Queries

Set $A_0=U_0=V_0=0$. Let $U_i$ be the number of operations of size $1$ covering position $i$, and let $V_i$ be the number of operations of size $X$ covering position $i$. Then

$$U_i+XV_i=A_i,$$

where $U_i$ and $V_i$ are nonnegative integers.

For fixed sequences $U,V$, the required number of operations is

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

This value is attainable by starting new intervals whenever a count increases and ending existing intervals whenever it decreases.

Let $F_i(c)$ be the minimum cost for positions $1$ through $i$ when $V_i=c$. Put . If the previous state is and , the transition cost is

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

The state must also satisfy $0\le c\le\lfloor A_i/X\rfloor$. Thus, $F_i$ is an integer discrete convex function.

For an integer discrete convex function $f$, define its conjugate by

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

For $1\le j\le X+1$, define

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

This is the smallest optimal position at slope $-X+j$.

We use the following properties.

• Conjugates add under infimal convolution, so the values $D_j$ also add.
• Restricting the domain to an integer interval $[0,q]$ changes $D_j$ to .

Write $\Delta=Xq+r$ with $0\le r<X$. Let $d_j(\Delta)=D_j(h_\Delta)$. If , then

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

If $\Delta<0$, then

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

The bracket is $1$ when its condition is true and $0$ otherwise. These formulas follow by examining the discrete slopes of $h_\Delta(e)-(-X+j)e$.

Let $z_j=D_j(F_{i-1})+d_j(\Delta_i)$ and . Then

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

If $\alpha_i=F_i^*(-X)$, then

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

We always have $D_1(F_i)=0$ and $D_{X+1}(F_i)=q_i$. The state never adds a negative term to . Therefore, only the states must be stored. The contribution of state can be included in a position-dependent constant.

Fix one stored state $j$. One position transforms an input state $x$ as

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

and adds $\min(x+d,0)$ to $\alpha$.

The effect of any contiguous segment can be represented by five integers:

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

where $t$ is the segment's contribution to $\alpha$. A single position has summary

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

Suppose the left summary is $(a_1,l_1,r_1,p_1,c_1)$ and the right summary is . Applying the left segment and then the right segment gives

$$\begin{array}{rl}{\displaystyle a}& {\displaystyle =a_1+a_2,}\\ {\displaystyle l}& {\displaystyle =\mathrm{clamp}(l_1+a_2,l_2,r_2),}\\ {\displaystyle r}& {\displaystyle =\mathrm{clamp}(r_1+a_2,l_2,r_2),}\\ {\displaystyle p}& {\displaystyle =p_1+\min (l_1+p_2,c_2),}\\ {\displaystyle c}& {\displaystyle ={}_{}}\end{array}$$

The states are independent, so merging two segment tree nodes takes $O(X)$ time.

At the root, every input state is $0$. The final value of a state is $\operatorname{clamp}(a,l,r)$, and its contribution to $\alpha$ is $\min(p,c)$. Finally, output

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

Read all queries in advance. If a position $p$ is ever updated, only transitions $p$ and $p+1$ can change. Let $S$ be the set of all such transition positions. Then $|S|\le2Q$.

Positions outside $S$ never change. Initially merge each maximal contiguous segment of such positions into one summary, while every position in $S$ remains a summary of length $1$. If the compressed sequence has length $K$, then

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

Build a segment tree on this compressed sequence. An update rebuilds only the compressed leaves corresponding to transitions $p$ and $p+1$.

The preprocessing time is $O(X(N+Q)+Q\log Q)$, the time per query is $O(X\log Q)$, and the memory usage is $$.

Solution written by GPT5