很好的题目。
首先我们假设 \(a\) 没有初始值，这貌似是平凡的。因为这样的话如果两个位置 \(x<y\) 那么 \(a_x\leq a_y\) 对于任意时刻都成立。取 \(\min\) 的过程只需要线段树上二分加上区间覆盖即可。
但是有初始值怎么办呢？这个问题开始变得棘手起来。但是我们发现上面那个性质在底下也部分成立：如果某个时刻存在 \(x<y\) 且 \(a_x\leq a_y\) ，那么之后 \(a_x\leq a_y\) 也都成立，因为无论是取 \(\min\) 还是加 \(i\) 都不能改变他们两个之间的大小关系。
假设没有 \(\min\) 操作显然很好维护，那么如果一个位置被取过 \(\min\) 了之后呢？发现所有取过 \(\min\) 的位置都是单调不降的，这就可以像没有初值的时候一样维护。因此，我们如果能求出每个位置第一次被取 \(\min\) 的时间，那么剩下的部分可以用一个线段树解决。
考虑整体二分，对于一个二分区间 \([l,r]\)，考虑其左区间是否能对当前区间的数造成影响，要求是 \(a_i+ic_j\geq v_j\)，其中 \(c_j\) 表示的是到 \(j\) 为之整体加了多少次。变形可以得到 \(v_j-ic_j\leq a_i\)，则可以对点 \((c_j,v_j)\) 构架下凸壳，然后拿斜率位 \(i\) 的直线去截，看最小截距和 \(a\) 的关系即可。时间复杂度 \(O(n\log n)\)，但是常数有一点点大。
标签：min,初始值,712,2021,UOJ,ic From： https://www.cnblogs.com/275307894a/p/17326834.html