Hopping Around the Array
Contest: Deltix Round, Spring 2021 (open for everyone, rated, Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: data structures, dp

William really wants to get a pet. Since his childhood he dreamt about getting a pet grasshopper. William is being very responsible about choosing his pet, so he wants to set up a trial for the grasshopper!

The trial takes place on an array $$$a$$$ of length $$$n$$$, which defines lengths of hops for each of $$$n$$$ cells. A grasshopper can hop around the sells according to the following rule: from a cell with index $$$i$$$ it can jump to any cell with indices from $$$i$$$ to $$$i+a_i$$$ inclusive.

Let's call the $$$k$$$-grasshopper value of some array the smallest number of hops it would take a grasshopper to hop from the first cell to the last, but before starting you can select no more than $$$k$$$ cells and remove them from the array. When a cell is removed all other cells are renumbered but the values of $$$a_i$$$ for each cell remains the same. During this the first and the last cells may not be removed.

It is required to process $$$q$$$ queries of the following format: you are given three numbers $$$l$$$, $$$r$$$, $$$k$$$. You are required to find the $$$k$$$-grasshopper value for an array, which is a subarray of the array $$$a$$$ with elements from $$$l$$$ to $$$r$$$ inclusive.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 20000$$$), the length of the array and the number of queries respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$)  – the elements of the array.

The following $$$q$$$ lines contain queries: each line contains three integers $$$l$$$, $$$r$$$ and $$$k$$$ ($$$1 \le l \le r \le n$$$, $$$0 \le k \le min(30, r-l)$$$), which are the edges of the subarray and the number of the grasshopper value respectively.

Output format:
For each query print a single number in a new line  — the response to a query.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For the second query the process occurs like this:

For the third query the process occurs like this:

Example input:
9 5
1 1 2 1 3 1 2 1 1
1 1 0
2 5 1
5 9 1
2 8 2
1 9 4

Example output:
0
2
1
2
2

Editorial:
Let's look into all jumps in the optimal answer except the last one with $$$k = 0$$$. Thereafter, from the position $$$i$$$ it is most effective to jump at such position $$$best$$$ that: $$$i \le best \le i+a_i$$$ and $$$a_{best} + best$$$ is the maximal possible. For each $$$i$$$ we can use a segment tree for maximum to find that optimal $$$best$$$.
Let's also notice that if we want to jump from position $$$i$$$ having done $$$x$$$ removals of cells which indices are from $$$i+1$$$ to $$$a_i+i$$$, then we want to end up in a cell $$$a_i+i+x$$$, because we can do fewer removals otherwise.
These observations are sufficient for us to use the idea of dynamic programming. Let $$$dp[t][i][k]$$$ store the maximal pair $$$(a_j + j, j)$$$ in which we can end up jumping from position $$$i$$$, having performed $$$2^t$$$ jumps and removed not greater than $$$k$$$ cells. With $$$t=0$$$ we can initialize the dynamic with optimal $$$best$$$. Now we will iterate over $$$t$$$, $$$i$$$ and $$$k$$$ in increasing order and see how to recalculate the dynamic. Let's iterate over $$$k1$$$ — the number of removals for the first $$$2^{t-1}$$$ jumps. Then, using the value $$$dp[t-1][i][k1]$$$ we know in which position we stopped. Now we need to perform $$$2^{t-1}$$$ jumps from that position having done not greater than $$$k-k1$$$ removals.
Additionally, let's make another dynamic $$$imax[t][i][k]$$$ — stores such maximal position of initial array in which we can end up jumping from position $$$i$$$, having performed $$$2^t$$$ jumps and removed not greater than $$$k$$$ cells. Just like for the previous dynamic we can initialize it using $$$best$$$, and then similarly recalculate the value of the dynamic, but using two dynamics this time — $$$imax$$$ and $$$dp$$$.
It is noteworthy that both dynamics need it to be supposed that when we start in element $$$i$$$ we do not remove it.
Let's see how we can answer the query using the calculated dynamics. To begin with, let's consider particular cases. If $$$l=r$$$, then the answer is equal to $$$0$$$. If $$$a_l + l + k \ge r$$$, then the answer is equal to $$$1$$$. Farther on, let's make one more dynamic $$$now_j$$$, in which we will maintain three numbers $$$(cnt, a_i + i, i)$$$. With that the first number is the number of jumps (we minimize it), two following numbers declare our current position $$$i$$$, and we maximize these two numbers as a pair $$$(a_i + i, i)$$$. Using that dynamic we wish to end up in the last but one cell of the optimal way, having removed not greater than $$$j$$$ cells. Initially, the values of dynamic are equal to $$$(0, a_l + l, l)$$$. Let's iterate over $$$t$$$ in decreasing order (which is to say, we iterate over the $$$2^t$$$ jumps). Let's create a dynamic $$$go$$$, which we are going to recalculate on the current step, and then make $$$now=go$$$ (in other words, we recalculate the dynamic $$$now$$$). Let's iterate over $$$k1$$$ — the number of removals during the preceding steps and $$$k2$$$ — the number of removals we are going to do on the current step. Using the value $$$now_{k1}$$$ we know in which position we stopped, and with dynamic $$$imax$$$ we can check if we cannot overjump $$$r$$$ (or end up in it) having performed $$$2^t$$$ jumps. If we cannot overjump $$$r$$$, then we will try to update the value $$$go_{k1+k2}$$$, otherwise, it's not profitable to perform the jump and thus let's update $$$go_{k1}$$$.
As a result, we have the calculated dynamic $$$now_j$$$. Let's iterate over it and find $$$j$$$-s such that we can jump to $$$r$$$ with one jump and take the minimal answer over these $$$j$$$-s (don't forget to add $$$1$$$, since we jumped to the last by one cell in the dynamic).
We calculate the dynamics in $$$O(n \cdot k^2 \cdot log(n))$$$, answer the query in $$$O(k^2 \cdot log(n))$$$, thus the solution is in $$$O((n + q) \cdot k^2 \cdot log(n))$$$.