与一维数组值域处理方法的区别
一维数组做值域题时可能会出现删除复杂度过高或者添加复杂度过高的情况,有时对于大型样例会超时,这时候我们就需要用到回滚莫队
传统莫队算法中,我们通常维护一个值域数组(桶数组)cnt[]来统计每个值的出现次数,并通过add()和remove()两个函数来动态维护当前区间。然而,这种方法存在一个根本性问题:添加操作和删除操作的时间复杂度可能不对称。
以一维数组维护区间最大值为例:
如上所示,添加操作是O(1)的,但删除操作在最坏情况下需要O(值域大小)的时间。这种不对称性在某些题目中会导致算法效率急剧下降。
回滚莫队正是为了解决这个问题而提出的。
回滚莫队通过以下策略解决不对称性问题:
基本策略
* 只实现添加操作(或只实现删除操作,但通常实现添加更简单)
* 不实现删除操作,当需要"删除"时,通过回滚到之前保存的状态
* 将查询按块排序,保证右端点单调递增
现在看看完整的代码(维护最大值,代码AI声明):
养成习惯,看完点赞!