题意概述

给定一个序列 $\{a_n\}$，$q$ 次操作，每次全局加系数非负的二次函数，询问全局最小值。

具体地，第 $j$ 次操作给定 $A_j, B_j, C_j$（$A_j, B_j, C_j \geq 0$），令所有 $a_i$ 变为 $a_i + A_j \times i^2 + B_j \times i + C_j$。

每次操作后输出 $\min_{1 \leq i \leq n}\{A_i\}$。

做法

注意到二次函数是不下降的，因此全局最小值下标是不上升的。我们可以通过二分来判断哪些时刻内最小值下标是否改变。

具体地，先求出初始条件下的全局最小值下标 $\text{minpos}$，然后二分计算最大的时间 $t$ 使得进行完编号为 $[1, t]$ 的全局加操作后 $\text{minpos}$ 不变。不断重复上述过程即可。

朴素实现为 $O((n + q) \log q)$。

问题

有没有线性（即 $O(n + q)$）的做法？