Replace and Sum

The operation direction is the whole problem.

You can replace $a_i$ by $a_{i+1}$, so values can only travel from right to left. Also, at any position $j$, you may inject the value $b_j$ by setting $a_j=b_j$.

That means position $i$ can eventually receive:

• the original value $a_j$ for any $j\ge i$, by copying $a_j$ left until it reaches $i$;
• the value $b_j$ for any $j\ge i$, by first doing $a_j=b_j$, then copying it left until it reaches $i$.

So position $i$ can become any value from

$$\{a_j,b_j\mid j\ge i\}.$$

Therefore the best value possible at position $i$ is

$$c_i=\max_{j\ge i}(a_j,b_j).$$

Now comes the part where it is easy to invent fake constraints. You might worry that choosing the best value for one position breaks another position. It does not matter. For a query $[l,r]$, we only care about the final values inside that segment, and we are allowed any number of operations. To set a specific position $i$ to its best value, choose a source $j\ge i$ containing that best value, set $a_j=b_j$ first if the source is from $b$, then copy left along $j-1,j-2,\dots,i$. This may overwrite positions on the path, but those positions can be fixed later by their own operations. Process positions from left to right if you want a concrete construction: fixing a larger index later is not affected by operations ending farther left. No conflict, no drama.

So every query asks for

$$\max \sum_{i=l}^{r} a_i=\sum_{i=l}^{r} c_i.$$

We can compute $c$ in one right-to-left pass. Let

$$mx_i=\max(mx_{i+1},a_i,b_i),$$

then $c_i=mx_i$.

After that, build prefix sums:

$$pref_i=pref_{i-1}+c_i.$$

Each query answer is

$$pref_r-pref_{l-1}.$$

Edge cases are boring in the best way:

• If $n=1$, the answer is just $\max(a_1,b_1)$.
• Multiple queries are independent; no query consumes operations or permanently changes the arrays.
• Values are small, but sums can reach about $2\cdot 10^9$, so use long long anyway. Cheap insurance.

Complexity per test case is

$$O(n+q)$$

time and

$$O(n)$$

memory.