E. Landscape Generator

Key Observations

• Every operation is purely additive, so the order does not matter. We only need the sum of all contributions at each position.

• A constant raise/depress on $[x_1, x_2]$ is just the linear function \[ 0 \cdot x + (\pm 1) \] on that interval.

• A hill or valley is piecewise linear. Let \[ m = \left\lfloor \frac{x_1 + x_2}{2} \right\rfloor. \] Then a hill on $[x_1, x_2]$ equals \[ x - x_1 + 1 \quad \text{for } x \in [x_1, m], \] and \[ x_2 - x + 1 \quad \text{for } x \in [m+1, x_2]. \] A valley is just the negative of the same profile.

• So every operation can be decomposed into at most two interval updates of a linear function \[ a x + b. \]

• If we keep two difference arrays, one for the active coefficient $a$ and one for the active coefficient $b$, then after a prefix sum we know the total linear function applying at each position.

Algorithm

1. Maintain two difference arrays:

   • diffA for slope coefficients,

   • diffB for constant coefficients.

   • An update ``add $ax+b$ on $[L,R]$'' is handled by \[ \texttt{diffA}[L] += a,\quad \texttt{diffA}[R+1] -= a, \] and similarly for diffB.

   • For R and D, add the constant functions $+1$ or $-1$ on $[x_1,x_2]$.

   • For H or V, let sign be $+1$ for a hill and $-1$ for a valley, and let $m=\lfloor (x_1+x_2)/2 \rfloor$. Then add \[ \texttt{sign} \cdot x + \texttt{sign}(1-x_1) \] on $[x_1,m]$, and \[ -\texttt{sign} \cdot x + \texttt{sign}(x_2+1) \] on $[m+1,x_2]$.

   • After processing all operations, sweep from left to right. Prefix-sum diffA and diffB into the current coefficients $A$ and $B$. The final height at position $i$ is then \[ A \cdot i + B. \] enumerate

     Correctness Proof

     We prove that the algorithm returns the correct answer.

     Lemma 1.

     For any interval $[L,R]$, the update ``add $ax+b$ for every $x \in [L,R]$'' is represented correctly by adding $a$ and $b$ to the two difference arrays at $L$ and subtracting them at $R+1$.

     Proof.

     After taking prefix sums of the difference arrays, coefficient $a$ is present exactly on indices in $[L,R]$, and absent elsewhere. The same is true for coefficient $b$. Therefore the value contributed at index $x$ is exactly $ax+b$ when $x \in [L,R]$ and $0$ otherwise. □

     Lemma 2.

     Let $m=\lfloor (x_1+x_2)/2 \rfloor$. A hill on $[x_1,x_2]$ is exactly the sum of the two linear pieces \[ x-x_1+1 \quad \text{on } [x_1,m] \] and \[ x_2-x+1 \quad \text{on } [m+1,x_2]. \] A valley is the negative of the same decomposition.

     Proof.

     For $x \in [x_1,m]$, the distance from $x$ to the nearer endpoint is $x-x_1$, so the hill adds $x-x_1+1$. For $x \in [m+1,x_2]$, the nearer endpoint is the right one, so the hill adds $x_2-x+1$. These are exactly the values specified in the statement: $1$ at both ends, increasing by $1$ toward the middle, with one peak for odd length and two equal middle values for even length. Negating the profile gives a valley. □

     Lemma 3.

     For every position $i$, the algorithm computes exactly the total contribution of all operations at $i$.

     Proof.

     By Lemma 2, each input operation is decomposed into one or two linear interval updates that reproduce its exact effect. By Lemma 1, each such linear interval update is represented exactly in the difference arrays. Summing all active coefficients at position $i$ therefore gives the sum of all operation contributions at $i$, which is the final height there. □

     Theorem.

     The algorithm outputs the correct answer for every valid input.

     Proof.

     Every input operation is transformed into an equivalent set of linear interval updates by Lemma 2. Those updates are accumulated exactly by the two difference arrays by Lemma 1. By Lemma 3, the final sweep computes the exact total height at every position. Therefore the algorithm outputs the correct landscape. □

     Complexity Analysis

     Each modification performs only $O(1)$ work, and the final sweep is linear. So the total running time is $O(n+k)$.

     The two difference arrays use $O(n)$ memory.

     Implementation Notes

     • The split point is always $m=\lfloor (x_1+x_2)/2 \rfloor$. This handles both odd and even interval lengths correctly.

     • Using 64-bit integers is important because many large hills or valleys can accumulate.

     • The second linear segment is empty when $x_1=x_2$; the helper simply skips empty intervals.