题目描述

小红正在做一个工程，她先写了份初版工程计划，但是经理不太满意，让小红改一改。

改着改着，小红就改了$32$ 版设计方案，然后经理说，还是用初版工程计划吧，现在小红非常的.....

思路：哈希表模拟

这道题如果使用线段树那就是变复杂了，可以观察到答案是具有二段性的，所以可以考虑将答案二分，那么我们假设当前要修改到第x版计划，那么要怎么快速知道修改到第x版计划后是否有人的怒火值超过阙值呢，因为每一次修改只会对一段人的怒火值全部加1，那么我们就可以使用差分，O(1)的进行加减，当修改完第x版计划后进行前缀和一一比对是否超出阙值即可

时间复杂度:$O(nlogm)$

代码

python