Sum of Fractions

Research basis: I checked the official Codeforces editorial page for Educational Round 188, the CF Step hints page, and a Codeforces blog post pointing to a video editorial: https://codeforces.com/blog/entry/152150, https://cfstep.com/codeforces/contests/contest-2204/problem-f/hints/, and https://codeforces.com/blog/entry/152250. The official tutorial text was not expanded on the page, but the official accepted code confirms the monotonic-stack contribution split and the same piecewise linear formula. The statement below is the real source of truth.

First solve the tiny problem: one fraction $\frac{1}{x}$, exactly $t$ operations.

Suppose the final denominator is $d$. We decreased the denominator $x-d$ times, so the numerator was increased

$t-(x-d)$

times. The final numerator is therefore

$1+t-(x-d)=t+1-x+d,$

and the value is

$\frac{t+1-x+d}{d}=1+\frac{t+1-x}{d}.$

Now the choice is obvious:

• if $t+1-x<0$, maximize $d$, so $d=x$, giving $\frac{t+1}{x}$;
• if $t+1-x\ge 0$, minimize $d$, so $d=1$, giving $t+2-x$.

At the boundary $t=x-1$, both give $1$, so using the implementation split

$$g_x(t)= \begin{cases} \frac{t+1}{x}, & t<x,\\ t+2-x, & t\ge x. \end{cases}$$

Now take a subarray. The important claim is that all $k$ operations should be spent on one fraction whose initial denominator is minimum in the subarray.

Why? For denominator $x$, the marginal gains of the optimized value are

$\underbrace{\frac{1}{x},\frac{1}{x},\dots,\frac{1}{x}}_{x-1\text{ times}},1,1,1,\dots$

If $x\le y$, then the marginal sequence for $x$ dominates the marginal sequence for $y$ at every position: $\frac1x\ge\frac1y$, and denominator $x$ reaches the $1$-gain phase no later than denominator $y$. Also the sequence is nondecreasing, so moving operations from a larger denominator to the smallest denominator never hurts. Splitting operations across fractions sounds democratic; mathematically, it is just leaving money on the table.

Therefore, for a subarray with minimum value $x$, pick one occurrence of that minimum and replace its base contribution $\frac1x$ by $g_x(k)$. Every other element just contributes its original $\frac1{a_i}$.

We need sum this over all subarrays without doing $O(n^2)$ work.

Assign every subarray to exactly one position containing its minimum. Use this tie rule: assign to the leftmost minimum. For each index $i$:

• $L_i$ = nearest index to the left with $a_{L_i}\le a_i$, or $-1$;
• $R_i$ = nearest index to the right with $a_{R_i}<a_i$, or $n$.

Then $i$ is the assigned minimum exactly for subarrays $[l,r]$ with

$L_i<l\le i\le r<R_i,$

so the count is

$c_i=(i-L_i)(R_i-i).$

These arrays come from two monotonic stacks. The asymmetric tie handling is not optional bookkeeping nonsense; it prevents duplicate equal minima from double-counting the same subarray.

Now split the answer into two parts.

For position $i$, the total number of subarrays containing it is

$(i+1)(n-i).$

In $c_i$ of them, $i$ is the special minimum and should be handled by $g_{a_i}(k)$. In all remaining subarrays containing $i$, it contributes normally as $\frac1{a_i}$. So define

$$\text{common}=\sum_i \left((i+1)(n-i)-c_i\right)\frac1{a_i}.$$

This part is independent of $k$.

For the special-minimum part, each index $i$ contributes over its $c_i$ assigned subarrays:

$$c_i g_{a_i}(k)= \begin{cases} c_i\frac{k+1}{a_i}, & k<a_i,\\ c_i(k+2-a_i), & k\ge a_i. \end{cases}$$

Both branches are linear in $k$. Since the queries $k_1\le k_2\le\dots\le k_m$ are sorted, find

$p_i=\min\{q: k_q\ge a_i\}$

by binary search. Add one linear function to query range $[0,p_i)$ and the other to $[p_i,m)$ using difference arrays for slope and constant term.

For $k<a_i$:

$c_i\frac{k+1}{a_i}=\left(c_i a_i^{-1}\right)k+c_i a_i^{-1}.$

For $k\ge a_i$:

$c_i(k+2-a_i)=c_i k+c_i(2-a_i).$

After applying all range additions, prefix the slope and constant arrays. For each query $k_q$:

$$\text{ans}(k_q)=\text{common}+\text{slope}_q\cdot k_q+\text{const}_q \pmod{998244353}.$$

Edge cases:

• $k=0$ works: $g_x(0)=\frac1x$.
• $a_i=1$ works: for $k\ge1$, $g_1(k)=k+1$ because the denominator cannot decrease.
• Equal minima work because the stack tie rule assigns each subarray once.
• Modular inverses exist because $1\le a_i\le 10^8<998244353$.

Complexity is $O((n+m)\log MOD+n\log m)$ time from modular inverses and binary searches, and $O(n+m)$ memory. With $5\cdot10^5$ elements, this is fine.