Inverse Minimum Partition (Hard Version)

Let $\operatorname{opt}(l,r)$ be the minimum partition cost of the subarray $a_l,\ldots,a_r$. We need

$$\sum_{r=1}^n\sum_{l=1}^r \operatorname{opt}(l,r).$$

The direct DP is obvious but useless:

$$\operatorname{opt}(l,r)=\min_{i=l}^{r}\left(\operatorname{cost}(l,i)+\operatorname{opt}(i+1,r)\right),$$

where $\operatorname{opt}(r+1,r)=0$. That is too many states if we store all $l$ for every $r$.

Two key facts

First, for fixed $r$, $\operatorname{opt}(l,r)$ is monotone:

$$\operatorname{opt}(l,r)\ge \operatorname{opt}(l+1,r).$$

Why? Removing the first element from a segment can only increase its minimum, so the segment cost cannot increase. In the DP above, every candidate for starting at $l$ is at least as expensive as the corresponding candidate after deleting $a_l$. So later starts are never worse.

Second, we only need segment costs $1,2,3$ in an optimal partition. Suppose a segment has cost $X\ge4$. Pick $y=2$ and $x=\lceil X/2\rceil$. Then

$$xy\ge X,\qquad x+y\le X.$$

Let the segment end with value $M$. Cut it right before the suffix where all values are at least $\lceil M/y\rceil$. The right part has cost at most $y$. The left part has last value below $M/y$, while the old whole segment had minimum large enough relative to $M/X$, so the left part has cost at most $x$. The two new costs sum to at most $X$, and both are smaller than $X$. Repeat this cleanup until no segment has cost above $3$.

So the scary cost function gets kneecapped: every transition only needs $k=1,2,3$.

The value range is tiny

For any fixed subarray ending at $r$, there is a crude greedy partition with cost at most $128$.

Build blocks from right to left. Suppose the current block must end at value $v$. Take the longest suffix whose minimum is at least $\lceil v/2\rceil$; that block has cost at most $2$. If this does not consume the whole remaining prefix, the next right endpoint is a value strictly below $v/2$. So the endpoint value halves each time. Since $a_i\le 10^{18}<2^{60}$, this happens at most about $60$ times, each costing at most $2$. Hence $128$ is safely above every possible optimum.

This is the whole trick: $l$ ranges over $n$ positions, but the answer value ranges over only $128$ values. Flip the DP, knapsack-style.

Precomputing segment starts

Define

$$L(i,k)=\min\{l:\operatorname{cost}(l,i)\le k\}.$$

For the segment $a_l,\ldots,a_i$,

$$\operatorname{cost}(l,i)\le k$$

is equivalent to

$$a_i\le k\cdot \min(a_l,\ldots,a_i).$$

So every value in the segment must be at least $\lceil a_i/k\rceil$. Therefore $L(i,k)$ is exactly one plus the last position $j\le i$ with

$$a_j<\left\lceil\frac{a_i}{k}\right\rceil,$$

or equivalently $k a_j<a_i$.

We compute all $L(i,k)$ for $k=1,2,3$ using a segment tree that finds the rightmost position with value below a threshold. Then build sparse tables over each $L(\cdot,k)$ so range minimum queries are $O(1)$.

The flipped DP

For fixed $r$, define

$$D[c]=\min\{l:\operatorname{opt}(l,r)\le c\}.$$

If no such $l$ exists, set $D[c]=r+1$. Also $D[0]=r+1$, since nonempty subarrays cost at least $1$.

Because $\operatorname{opt}(l,r)$ is monotone in $l$, starts with value at most $c$ form a suffix:

$$D[c],D[c]+1,\ldots,r.$$

So the number of starts with exact value $c$ is

$$D[c-1]-D[c].$$

That gives the contribution for this $r$ once all $D[c]$ are known.

Now compute $D[c]$. Choose the first segment of the partition: it is $a_l,\ldots,a_i$, and let its cost budget be $k\in\{1,2,3\}$. We must have $k\le c$; do not let a cost-$2$ segment sneak into budget $1$, unless you enjoy getting slapped by the test $[3,5]$.

The remaining suffix $a_{i+1},\ldots,a_r$ must have optimum at most $c-k$. This means

$$i+1\ge D[c-k],$$

so

$$i\ge D[c-k]-1.$$

For any valid $i$, the earliest possible $l$ for the first segment is $L(i,k)$. Therefore

$$D[c]=\min\left(D[c-1],\min_{1\le k\le \min(3,c)}\min_{\max(1,D[c-k]-1)\le i\le r} L(i,k)\right).$$

The outer $D[c-1]$ just says if a start works with smaller budget, it also works with budget $c$.

Each inner minimum is one RMQ. There are only $128$ budgets and $3$ costs, so each right endpoint costs constant-ish time.

Complexity

Precomputing $L$ and sparse tables costs $O(n\log n)$. The DP costs $O(128\cdot 3\cdot n)$, which is just linear with a chunky constant. Memory is $O(n\log n)$.