题目

传送门= ̄ω ̄=

题解

显然线段树是可以的,搞m次区间修改、区间最小值查询即可。
复杂度$O(mlogn)$
然而听说普通线段树被卡常,不加读入优化70分,加读入优化95,得用zkw线段树。
所以我打了差分,复杂度只有$O(n+m)$,理论上不存在更优的做法了,因为输入复杂度就是$O(n+m)$了。
设$f[i]=r[i]-r[i-1]$,
那么每次修改区间$[l,r]$,区间减d,则只要$f[l]-=d,f[r]+=d$
然后我们区间修改了m次以后,还原r[i]的值($r[i]=f[1]+f[2]+...+f[i]=r[i-1]+f[i]$),如果某个r[i]<0的话,就依次从第m个修改开始撤销,直到这个r[i]>=0了。
撤销也是一样,只要$f[l]+=d,f[r]-=d$,然后如果$l\leq i\leq r$的话$r[i]+=d$。
这样最后答案就是最后一个撤销的修改的序号了。
当然如果没撤销,输出0即可。

代码: