浅谈回滚莫队
BFqwq
2020-10-29 20:25:18
## 回滚莫队
前置知识：莫队。
不会的同学可以看[往期日报](https://www.luogu.com.cn/blog/codesonic/Mosalgorithm)
回滚莫队，听起来好像很高级的样子。
但其实，它还有个很平凡的名字——不删除莫队。
回顾普通的莫队，其实说到底一共只有四个操作，分别是 $l++,l--,r++,r--$。
而这些操作实际上又分成两大类，分别是插入和删除。
简单的说，当我们执行完 $l--$ 或是 $r++$ 的操作后，我们的区间变长了，相当于我们向区间内插入了一个数。
而另外两个操作之后呢，我们的区间变短了，相当于我们从区间中删除了一个数。
虽然在平时的莫队中，这两者的复杂度是一样的，但显然，删除的操作往往更为复杂，甚至有的时候我们能很简单的完成插入操作，但却一直想不到如何进行删除。这个时候，我们的回滚莫队就要登场了。
我们先通过一个比较简单的例子来了解一下回滚莫队。
### 区间众数问题
给定一个序列以及若干次询问，求区间众数，可离线。
这个问题是个经典的问题，目前有许多的解法。但从思维难度上来讲，回滚莫队可能是最简单的。
考虑莫队。我们维护一个 $f$ 数组代表出现次数，当我们要插入一个数时，我们只需要更新这个数的次数，然后和最大值作比较。这是大家都能想到的。
但要删除一个数就显得比较复杂，于是我们可以对莫队作一点变化。
首先，对于左右端点位于一个块内的询问，我们直接暴力，这样的复杂度显然正确。
接着，我们依然按照左端点排序，将左端点在同一个块内的数拿出来一起处理。
我们直接将右指针移到该左端点所在块的**右端点**处，然后暴力向右插入。这样，在块外的部分的贡献我们就可以统计了。
然后我们将**状态保存**，然后将左指针移到左端点所在块的**右端点 $+1$** 处，向左插入，将块内的部分的贡献加入。
然后，我们再将左端点逐个移回，并**撤销**左区间的贡献即可。注意这里是撤销，而不是删除。
具体的实现方法很多，比如我们在右端点时将区间众数答案保存（定义一个变量 $lst=ans$），然后左端点插入时修改 $f$ 数组，撤回时依然修改 $f$ 数组，然后将答案变回（$ans=lst$）。
这样，我们的 $f$ 数组和 $ans$ 最终都没有发生变化，而左指针又回到了左端点所在块的右端点 $+1$，就好像什么也没有发生。
右端点的复杂度之和显然是 $\operatorname O(n\sqrt n)$，和莫队相同。而左端点由于每次的移动不超过 $\sqrt n$，顾复杂度为 $\operatorname O(m\sqrt n)$。因此，莫队的复杂度没有发生任何变化。
以上就是回滚莫队的基本内容，通过巧妙的变换莫队的指针位置来避免了删除操作。
当然实际上我们也可以类似的弄一个不插入莫队（这个名字是自己取的qaq），但由于一般很少见到插入比删除麻烦的题，所以实际作用不大。
下面我们来做几道题练练手。
### AT1219 歴史の研究
https://www.luogu.com.cn/problem/AT1219
实际上，这个题和区间众数的区别不是很大，只不过是在更新答案的时候再乘以一个 $X_i$。
和区间众数一样，我们维护一个数的出现次数。然后跑回滚莫队。更新答案时用事件的发生次数乘以重要度，与目前答案取最大值作为答案。
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
register int x=0;
register bool f=0;
register char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+c-48;
c=getchar();
}
return f?-x:x;
}
char cr[200];int tt;
inline void print(int x,char k='\n') {
if(!x) putchar('0');
if(x < 0) putchar('-'),x=-x;
while(x) cr[++tt]=x%10+'0',x/=10;
while(tt) putchar(cr[tt--]);
putchar(k);
}
const int maxn=1e6+10;
const int blk=405;
int n,a[maxn],m,bl[maxn],cnt[maxn];
int L[maxn],R[maxn],ans[maxn],mx,lst;
int lsh[maxn],len,c[maxn],del;
bool flag=0;
struct query{
int l,r,id;
friend bool operator <(query c,query d){
if(bl[c.l]==bl[d.l]) return c.r<d.r;
return c.l<d.l;
}
}q[maxn];
int chk(int l,int r){
mx=0;
for(int i=l;i<=r;i++){
cnt[c[i]]++;
mx=max(a[i]*cnt[c[i]],mx);
}
for(int i=l;i<=r;i++) cnt[c[i]]--;
return mx;
}
signed main(){
n=read();m=read();
int lxl=1;
L[1]=1;
while(L[lxl]+blk<n){
R[lxl]=L[lxl]+blk-1;
lxl++;
L[lxl]=R[lxl-1]+1;
}
R[lxl]=n;
for(int i=1;i<=lxl;i++){
for(int j=L[i];j<=R[i];j++){
bl[j]=i;
}
}
for(int i=1;i<=n;i++){
a[i]=lsh[i]=c[i]=read();
}
sort(lsh+1,lsh+n+1);
len=unique(lsh+1,lsh+n+1)-lsh-1;
for(int i=1;i<=n;i++)
c[i]=lower_bound(lsh+1,lsh+len+1,c[i])-lsh;
for(int i=1;i<=m;i++){
q[i].l=read();q[i].r=read();q[i].id=i+del;
if(bl[q[i].l]==bl[q[i].r]){
ans[i+del]=chk(q[i].l,q[i].r);
i--,m--,del++;
}
}
sort(q+1,q+m+1);
int l,r;
for(int i=1;i<=m;i++){
if(bl[q[i].l]!=bl[q[i-1].l]||i==1) flag=1;
if(flag){
memset(cnt,0,sizeof(cnt));
r=R[bl[q[i].l]];mx=lst=0;
flag=0;
}
while(r<q[i].r){
r++;
cnt[c[r]]++;
mx=lst=max(lst,cnt[c[r]]*a[r]);//lst代表答案存档
}
l=R[bl[q[i].l]]+1;
while(l>q[i].l){
l--;
cnt[c[l]]++;
mx=max(mx,cnt[c[l]]*a[l]);
}
ans[q[i].id]=mx;
mx=lst;//答案先更新回去
l=R[bl[q[i].l]]+1;
while(l>q[i].l){
l--;
cnt[c[l]]--;//左边部分出现次数减去
}
}
for(int i=1;i<=m+del;i++) print(ans[i]);
return 0;
}
```
### P5906 【模板】回滚莫队&不删除莫队
考虑维护每个数最左、最右出现的位置。
在右移指针的时候，直接更新最右出现的位置，然后如果目前还没有出现过这个数，就更新最左出现的位置，否则用右减左更新答案。这样，我们就得到了右边区间的贡献。
然后保存答案，移动左指针。在移动左指针时，我们只需要更新最右端点（如果这个数在右边没有出现过），不需要更新最左端点，因为目前左指针的点一定是区间中最左的点。
当我们更新完答案之后，我们对左指针的移动进行撤销操作。由于我们只更新了最右端点，并且是只更新了右侧没有出现过的数的右端点，所以我们只需要对这类数进行撤销。具体的操作就是：
```cpp
if(mx[a[l]]==l){
mx[a[l]]=0;
}
```
然后在每个块结束的时候，要对目前的最左最右两个数组作清除操作。
```cpp
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int read(){
bool f=1;
int x=0;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=0;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)-48+c;
c=getchar();
}
return f?x:x*-1;
}
char cr[200];int tt;
inline void print(register int x,register char k='\n') {
if(!x) putchar('0');
if(x < 0) putchar('-'),x=-x;
while(x) cr[++tt]=x%10+'0',x/=10;
while(tt) putchar(cr[tt--]);
putchar(k);
}
const int maxn=2e5+10;
const int blk=460;
int L[maxn],R[maxn],bl[maxn],l,r,len;
int n,m,a[maxn],del,res,lsh[maxn];
int mn[maxn],mx[maxn],ans[maxn],clr[maxn];
struct que{
int l,r,id;
friend bool operator <(que x,que y){
return bl[x.l]^bl[y.l]?x.l<y.l:x.r<y.r;
}
}q[maxn];
signed main(){
n=read();
int lxl=1;
L[1]=1;
while(L[lxl]+blk<n){
R[lxl]=L[lxl]+blk-1;
lxl++;
L[lxl]=R[lxl-1]+1;
}
R[lxl]=n;
for(int i=1;i<=lxl;i++){
for(int j=L[i];j<=R[i];j++){
bl[j]=i;
}
}
for(int i=1;i<=n;i++){
a[i]=lsh[i]=read();
}
sort(lsh+1,lsh+n+1);
len=unique(lsh+1,lsh+n+1)-lsh-1;
for(int i=1;i<=n;i++){
a[i]=lower_bound(lsh+1,lsh+len+1,a[i])-lsh;
}
memset(mn,0x3f,sizeof(mn));
m=read();
for(int i=1;i<=m;i++){
q[i].l=read();q[i].r=read();
q[i].id=i+del;
if(bl[q[i].l]==bl[q[i].r]){
for(int j=q[i].l;j<=q[i].r;j++){
if(mn[a[j]]<j){
ans[q[i].id]=max(ans[q[i].id],j-mn[a[j]]);
}
else mn[a[j]]=j;
}
for(int j=q[i].l;j<=q[i].r;j++){
mn[a[j]]=inf;
}
del++;i--;m--;
}
}
sort(q+1,q+m+1);
for(int k=1,i=1;k<=lxl;k++){
l=R[k]+1,r=R[k],res=0;
while(bl[q[i].l]==k){
while(r<q[i].r){
r++,mx[a[r]]=r;
if(mn[a[r]]==inf){
mn[a[r]]=r;
}
else{
res=max(res,r-mn[a[r]]);
}
}
ans[q[i].id]=res;
while(l>q[i].l){
l--;
if(mx[a[l]]){
ans[q[i].id]=max(ans[q[i].id],mx[a[l]]-l);
}
else mx[a[l]]=l;
}
while(l<=R[k]){
if(mx[a[l]]==l){
mx[a[l]]=0;
}
l++;
}
i++;
}
memset(mn,0x3f,sizeof(mn));
memset(mx,0,sizeof(mx));
}
for(int i=1;i<=m+del;i++){
print(ans[i]);
}
return 0;
}
```
### SP20644 ZQUERY - Zero Query
其实，这个题和上一题区别并不大。
我们先对数组做个前缀和，然后我们发现，$[l,r]$ 区间和是 $0$ 就等同于 $l-1,r$ 两个数的前缀和相等，于是方法就同上题了。
注意这里是从 $sum_r-sum_{l-1}=0$ 而不是 $sum_r-sum_{l}=0$。
不同的是，前缀和可能会是负数，因此我们可以加一个相同的数，使其变为正数，就可以放到数组维护了。
另外，如果我们查询的区间是 $[l,r]$，我们需要将 $l-1$ 也考虑进来，否则我们无法表示从 $l$ 开始的区间。
```cpp
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int read(){
bool f=1;
int x=0;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=0;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)-48+c;
c=getchar();
}
return f?x:x*-1;
}
char cr[200];int tt;
inline void print(register int x,register char k='\n') {
if(!x) putchar('0');
if(x < 0) putchar('-'),x=-x;
while(x) cr[++tt]=x%10+'0',x/=10;
while(tt) putchar(cr[tt--]);
putchar(k);
}
const int maxn=52233;
const int blk=320;
int L[maxn],R[maxn],bl[maxn],st[maxn],l,r;
int n,m,a[maxn],del,top,res;
int mn[maxn<<1],mx[maxn<<1],ans[maxn],clr[maxn];
struct que{
int l,r,id;
friend bool operator <(que x,que y){
return bl[x.l]^bl[y.l]?x.l<y.l:x.r<y.r;
}
}q[maxn];
signed main(){
n=read();m=read();
int lxl=1;
L[1]=1;
while(L[lxl]+blk<n){
R[lxl]=L[lxl]+blk-1;
lxl++;
L[lxl]=R[lxl-1]+1;
}
R[lxl]=n;
for(int i=1;i<=lxl;i++){
for(int j=L[i];j<=R[i];j++){
bl[j]=i;
}
}
a[0]=maxn;
for(int i=1;i<=n;i++){
a[i]=read()+a[i-1];
}
memset(mn,0x3f,sizeof(mn));
for(int i=1;i<=m;i++){
q[i].l=read();q[i].r=read();
q[i].id=i+del;
if(bl[q[i].l]==bl[q[i].r]){
mn[a[q[i].l-1]]=q[i].l-1;
for(int j=q[i].l;j<=q[i].r;j++){
if(mn[a[j]]<j){
ans[q[i].id]=max(ans[q[i].id],j-mn[a[j]]);
}
else mn[a[j]]=j;
}
mn[a[q[i].l-1]]=inf;
for(int j=q[i].l;j<=q[i].r;j++){
mn[a[j]]=inf;
}
del++;i--;m--;
}
}
sort(q+1,q+m+1);
for(int k=1,i=1;k<=lxl;k++){
l=R[k]+1,r=R[k],res=0,top=0;
while(bl[q[i].l]==k){
while(r<q[i].r){
r++,mx[a[r]]=r;
if(mn[a[r]]==inf){
mn[a[r]]=r,st[top++]=a[r];
}
else{
res=max(res,r-mn[a[r]]);
}
}
ans[q[i].id]=res;
while(l>=q[i].l){
l--;
if(mx[a[l]]){
ans[q[i].id]=max(ans[q[i].id],mx[a[l]]-l);
}
else mx[a[l]]=l;
}
while(l<=R[k]){
if(mx[a[l]]==l){
mx[a[l]]=0;
}
l++;
}
i++;
}
while(top--){
mn[st[top]]=inf,mx[st[top]]=0;
}
}
for(int i=1;i<=m+del;i++){
print(ans[i]);
}
return 0;
}
```
-----
理论上来说，回滚莫队由于不用删除，所以可以替代所有的普通莫队。由于其思路简单，所以在实际应用的时候可能有一定的优势。
但目前的 OI 中，直接使用回滚莫队进行操作的题目并不多，大部分的题目都可以用普通莫队解决，所以这一算法的实用性不是很强。
最后，这里给出两道个人认为比较有难度的回滚莫队题，有兴趣的同学可以自行思考。
- [P6072 『MdOI R1』Path](https://www.luogu.com.cn/problem/P6072)
- [P6580 [Ynoi2019]美好的每一天~不连续的存在](https://www.luogu.com.cn/problem/P6580)