【学习笔记】回滚莫队初步总结
LinkyChristian
·
·
个人记录
什么是回滚莫队啊（战术后仰）
首先确定一个常数len(一般而言取 \sqrt{n} ,n^{\frac{2}{3}})，将数组分为\lceil {\frac{n}{len}} \rceil个块 对于m个区间询问，将其按照左端点l所属的块从小到大排序，然后对于左端点在同一个块内的数据吗，将右端点r按从小到大排序
然后枚举每个块，让我们来处理所有左端点在这个块内的询问
我们知道一个性质，左端点在同一个块内的询问，右端点从左到右排序，所以右端点是单调的，我们用一个不会回退的指针rr来统计右边的结果
现在来考虑左端点，虽然左端点是无序的，但是由于它们都在同一个块内，所以它们离这个块的右端点的距离都不会超过len，所以我们用一个可以回退的指针 ll 来统计左边的答案
由于同一个块内的询问的右端点是递增的，因此 rr 产生的贡献在统计这个块内询问时是永久的，不用删除，而左端点是无序的，产生的贡献需要删除。
，注意 $ll$ 统计的贡献是临时的，因此统计完之后要让$ll$从此询问的左端点回归到块的右端点，同时删除贡献。
以下是需要注意的几点
1. 需要有一个不会归零的量记录$rr$统计到的贡献
2. 左右端点在同一个块内的询问可以直接暴力，反正也就O（$len$）的复杂度
来考虑复杂度，对于一个区块内的询问，指针 $rr$ 最多从这个区块右端点移动的序列右端点，最多移动 $n$ 次，最多有$\lceil {\frac{n}{len}} \rceil$个区间，所以复杂度最多为O（$nlen$）。
对于单个询问，指针 $ll$ 在这个块内移动，每个询问最多移动$len$ 次，对于所有的 $m$ 个询问，最多移动O（$mlen$）次。
因为 $m$ ， $n$同级，可以证明算法的复杂度为O（$nlen$）,大多数情况复杂度为O（$n\sqrt n$）
回滚莫队有一个好处，即只需要增操作，不需要减操作，对与某些无法实现减操作（比如查询最大值）的题目尤其好用
例题：[P3380【模板】回滚莫队&不删除莫队](https://www.luogu.com.cn/problem/P5906)
```cpp
#include<bits/stdc++.h>
#define N 200010
using namespace std;
int n,m,a[N],las[N],tmp[N],qlen,qn,bel[N],mr[N],ans[N],st[N],ed[N],num[N],cnt;
struct node{
int l,r,id;
}qt[200010];
bool cmp(node a1,node a2) {return (bel[a1.l]==bel[a2.l])?(a1.r<a2.r):(bel[a1.l]<bel[a2.l]);}
int calc(int l,int r) {
int res=0;
for(int i=l; i<=r; i++) las[a[i]]=0;
for(int i=l; i<=r; i++) (las[a[i]]==0)?(las[a[i]]=i):(res=max(res,i-las[a[i]]));
return res;
}
int main()
{
cin>>n;
qlen=sqrt(n);
for(int i=1; i<=n; i++) {
cin>>a[i];
tmp[i]=a[i],bel[i]=(i-1)/qlen+1;
mr[bel[i]]=i;
}
qn=bel[n],mr[bel[n]]=n;
sort(tmp+1,tmp+n+1);
int tn=unique(tmp+1,tmp+n+1)-tmp-1;
for(int i=1; i<=n; i++) a[i]=lower_bound(tmp+1,tmp+tn+1,a[i])-tmp;
cin>>m;
for(int i=1; i<=m; i++) {
cin>>qt[i].l>>qt[i].r;
qt[i].id=i;
}
sort(qt+1,qt+m+1,cmp);
int now=1;
for(int i=1; i<=qn; i++) {
int l=mr[i]+1,r=l-1,mx=0;
cnt=0;
while(bel[qt[now].l]==i) {
if(bel[qt[now].r]==i) {
ans[qt[now].id]=calc(qt[now].l,qt[now].r),now++;
continue;
}
while(r<qt[now].r) {
r++;
ed[a[r]]=r;
if(!st[a[r]]) st[a[r]]=r,num[++cnt]=a[r];
mx=max(mx,r-st[a[r]]);
}
int t1=mx;
while(l>qt[now].l) {
l--;
if(!ed[a[l]]) ed[a[l]]=l;
else mx=max(mx,ed[a[l]]-l);
}
ans[qt[now].id]=mx;
while(l<=mr[i]) {
if(ed[a[l]]==l) ed[a[l]]=0;
l++;
}
mx=t1;
now++;
}
for(int j=1; j<=cnt; j++) st[num[j]]=ed[num[j]]=0;
}
for(int i=1; i<=m; i++) cout<<ans[i]<<endl;
return 0;
}
```
[AT1219歴史の研究](https://www.luogu.com.cn/problem/AT1219)
```cpp
#include<bits/stdc++.h>
#define N 500010
using namespace std;
long long n,q,a[N],bel[N],qlen,mr[N],ans[N],bac[N],num[N],cnt,bac2[N],tmp[N],dui[N];
struct node{
long long l,r,id;
}pt[100010];
bool cmp(node a1,node a2) {
return (bel[a1.l]==bel[a2.l])?(a1.r<a2.r):(bel[a1.l]<bel[a2.l]);
}
long long calc(long long l,long long r) {
long long res=0;
for(long long i=l; i<=r; i++) bac2[a[i]]=0;
for(long long i=l; i<=r; i++) bac2[a[i]]+=dui[a[i]],res=max(res,bac2[a[i]]);
return res;
}
int main()
{
cin>>n>>q;
qlen=sqrt(n);
for(long long i=1; i<=n; i++) {
cin>>a[i];tmp[i]=a[i];
bel[i]=(i-1)/qlen+1,mr[bel[i]]=i;
}
sort(tmp+1,tmp+n+1);
int tn=unique(tmp+1,tmp+n+1)-tmp-1;
for(int i=1; i<=n; i++) {
int tp=a[i];
a[i]=lower_bound(tmp+1,tmp+tn+1,a[i])-tmp;
dui[a[i]]=tp;
}
for(long long i=1; i<=q; i++) {
cin>>pt[i].l>>pt[i].r;
pt[i].id=i;
}
sort(pt+1,pt+q+1,cmp);
long long now=1;
for(long long i=1; i<=bel[n]; i++) {
long long l=mr[i]+1,r=l-1,mx=0;
cnt=0;
while(bel[pt[now].l]==i) {
if(bel[pt[now].r]==i) {
ans[pt[now].id]=calc(pt[now].l,pt[now].r);
now++;continue;
}
while(r<pt[now].r) r++,bac[a[r]]+=dui[a[r]],mx=max(mx,bac[a[r]]),num[++cnt]=a[r];
long long tp=mx;
while(l>pt[now].l) l--,bac[a[l]]+=dui[a[l]],mx=max(mx,bac[a[l]]);
ans[pt[now].id]=mx;
while(l<=mr[i]) bac[a[l]]-=dui[a[l]],l++;
now++,mx=tp;
}
for(long long j=1; j<=cnt; j++) bac[num[j]]=0;
}
for(long long i=1; i<=q; i++) cout<<ans[i]<<endl;
return 0;
}
```
_upd2022/1/20:只删回滚莫队_
与前面提到的只加回滚莫队相反，只删回滚莫队通过将询问左端点按块递增排序，将左端点在同一个块内的询问按右端点降序排序，$l$ 指针复位时回到块的最左端而不是最右端， $r$ 指针从右往左扫来实现只有删除操作的效果。
例题：[P8078 [WC2022] 秃子酋长](https://www.luogu.com.cn/problem/P8078)
这种莫队的例题比较稀少，目前也只找到一道。