题解：CF377E Cookie Clicker

除排序外线性做法。

参考了 ${l\color{Red} oveJY}$ 大神的题解：文章链接。

我们发现，有一些工厂一定是不优的：按照 $c_{i}$ 升序（$c_{i}$ 相同按照 $v_{i}$ 降序）排序后，$v_{i}<=premax(v)$ 的一定是可以删除的。

之后我们就得到了一个 $c_{i}$ 和 $v_{i}$ 都严格上升的序列。

现在设函数：

${\Large F(t)}$。

横坐标为时间 $t$，纵坐标是金币数 $sum$。

容易发现，我们的操作顺序总是先取 $\mathbf{c_{i}}$ 小的，直到钱够了再取大的。

又有贪心结论：一个工厂如果被购买，则一定在能取用的第一时间（即当前总金币数 $sum \ge c_{i}$ 时）购买启动。

易知 $F(t)$ 是单调递增，且下凸的。

初始时 $F(t)$ 为一条直线 $sum=0$。

有了这个这两个结论，我们可以考虑增量构造函数 $F(t)$。

首先我们从工厂 $1$ 开始，顺序构造（大的一定在后面，以这个基础确定第一次出现的位置）。

每次对于当前的工厂，找到最早的时间 $t$ 使得 $F(t) \ge c_{i}$，这就是本工厂的启动时间，根据贪心结论，这个时间的固定的。

再确定这个工厂能影响的区间：

把这个区间全部变为这条直线就可以了。

由于整个函数是由很多直线（射线）构成的，使用单调栈维护就行，每次从栈底向顶找 $F(t)\ge c_{i}$，再把栈顶不优的全部弹掉，由于 $c_{i}\uparrow$，所以栈底指针也是单调增的（注意边界情况，实际写的时候最好找到了之后 bottom--）。

复杂度线性对数，瓶颈在于排序，实测跑得比二分快 $500ms$。

最后扫一遍函数找到第一个 $F(t)\ge S$ 的位置就好了。

P.S. 实际上本题对于下凸性质并没有利用，而是利用了单调性。

Code。