回滚莫队
定义
先来看一道题目
- 给定序列，若干个\([l,r]\)查询求\(max\{t*[t出现的次数]\}\)
回滚莫队解决的问题通常具有：动态加点易求，动态删掉难求；允许离线
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。为了防止每次查询都重新处理一遍，我们通过某种排序方法实现
做法
预处理分块，左端点处理同一块的一起处理，右端点一起处理
如果左右端点处理同一块则暴力处理，\(O(n\sqrt{n})\)
右端点递增随便处理就行，每个块最多往右移\(O(n)\)，\(O(n\sqrt{n})\)
每次处理完一个查询后又让左端点回到这个块的右边那个点，下一次查询再往左走，每个查询最多往左移\(O(\sqrt{n})\)，\(O(n\sqrt{n})\)
- 总时间复杂度\(O(n\sqrt{n})\)
更多精彩
