考虑加速求出它们的过程。以求出左边的最长前缀为例，设右边操作了 k 次，最长可以满足到 [1,f_k - 1]，并剩下 g_k 次操作。那么求解的过程即为依次考虑 i = 1 \rightarrow n，并记录现在需要的操作总次数 x = k：
若 a_i \le x，不需要任何操作。
否则，若 x + \lceil \dfrac {x-a_i}{c+1} \rceil \le ans，则 x \leftarrow x + \lceil \dfrac {x-a_i}{c+1} \rceil。
否则，f_k \leftarrow i，g_k \leftarrow ans - x，退出。
如果到最后 f_k,g_k 都没被赋值，那么 f_k = n+1。
那么考虑这个过程能否加速维护，即对所有的 k \in [0,ans] 一起维护这个过程，维护每一个 x_k 为对应 k 的 x 值，那么还是上面的过程，初始有 x_k = k，每次会对每个 k 进行 x_k \leftarrow x_k + \lceil \dfrac {\max(0,x_k-a_i)}{c+1} \rceil，发现后面增加的那个式子在 x_k 增加 1 时至多增加 1，因此可以归纳发现 x 数组一直满足 x_k \le x_{k+1} \le x_k + 1。
因此转而维护 x 的连续段，维护一个 x_0 和一个位置数组 a_1 < a_2 < \cdots < a_p，为 x 数组满足 x_k = x_{k-1} + 1 的 k 的位置，初始 p = ans + 1，a_i = i，注意最后有一个超出上界的位置以记录 x 数组的结尾。
那么每次的操作为：
若 x_0 \ge a_i，不需要操作。
设 y = \lceil \dfrac {x_0-a_i}{c+1} \rceil，并利用上面相除的余数可以找到第一个 x 值是 c+1 的倍数的对应位置 a_q，那么 \forall j \in [0,y)，删除 a_{q + (c+1)j}，如果这个位置已经超出了 p 的范围，那么对 [a_{p-1},a_p) 更新 f_* = i,g_* = ans - x_0 + p - 1 并删除最后一个元素，最后 x_0 \leftarrow x_0 + y。
实现时注意应该先算出需要删除多少次最后一个元素并先删除更新答案再做前面的普通删除，否则可能会因前面的删除而影响更新答案的区间情况，在 a 数组删完时及时退出。
qoj 上官方题解说由于每次都是隔 O(c) 个删一个所以每次删除后暴力更新 a 数组是 O(mc) 的，不懂，感觉有可能一次删除只删去了前面的一小部分，但这里使用数据结构维护并不难，发现 a 数组需要做的就是删去某个元素和查询排名为 a 的数，使用平衡树或权值线段树即可维护，可以用树状数组维护对应的权值线段树，这样常数小。
设 n,m 同阶，此时单次 check 的复杂度是 O(n \log n) 的，因此总复杂度为 O(n \log^2 n)，无法通过，但继续观察刚才维护的过程，发现 ans 对 a 数组的变化的影响并不大，ans 只影响被删除的后缀情况，因此可以考虑将计算到每个 i 时发生的删除位置都预处理出来，然后每次 check 的时候就相当于只需要维护删除一个数和查询最后一个数，因为每次还需要重新考虑从最后删除并更新答案的情况，那么这个只需要给值域开一个并查集就可以了，以此平衡到 O(n \log n)。