Can Some Explain on How to solve this problem. 488D - Strip

I understood the recurrence relation given in the editorial but I do not know understand how to use Sparse Table or Segment Tree ( Or the Monotonic Queue ) to calculate the function $$$f[i]$$$ and $$$g[i]$$$.

According to the recurrence $$$f[i] = min(f[k])+1;$$$ where $$$k \in [i-g[i],i-l]$$$

And $$$g[i]$$$ is the greatest length of the sequence ending ( and including ) at $$$i$$$ and satisfying the properties.

How will we Calculate $$$g[i]$$$ and $$$f[i]$$$ ?

Update : I Got it. Maybe I'll give a brief description of how it works.

==================================================================================

Solution.

Suppose we had a Data Structure that could give us the minimum in a dynamic range. Now, for calculating the function $$$g[j]$$$ let's iterate over right to left. Since $$$g[j]$$$ denotes the minimum $$$i$$$ ( and hence maximum length ) such that the range $$$\in [i,j]$$$ satisfies the condition $$$max_{i,j}-min_{i,j} \leq s$$$. We the observe the following structure.

$$$g[j-1] \leq g[j]$$$

Proof.

Let's say $$$g[j] = i$$$, now to calculate $$$g[j-1]$$$ ( i.e Removing the jth element) 3 cases arise.

• $$$jth$$$ element is $$$max_{i,j}$$$,

• $$$jth$$$ element is $$$min_{i,j}$$$,

• None of these.

The last case won't affect the situation and since we the interesed in $$$max_{i,j-1} - min_{i,j-1}$$$ we can observe in either of the first two cases $$$max_{i,j-1}$$$ will decrease or $$$min_{i,j-1}$$$ will increase. Hence $$$g[j-1]$$$ will be atmost equal to $$$g[j]$$$.

This inequality gives in the impression of using the two pointers technique and hence $$$g[i]$$$ can be calculated in amortized $$$O(n)$$$. Now for calculating $$$f[i]$$$, it's the minimum in the range $$$ \in [i-g[i],i-l] + 1$$$ which directly translates into sliding window mininum.

You can use a Segment Tree or Monotonic Queue to find the minimum and maximum in a running window.