回滚莫队
回滚莫队
介绍
在一些用莫队处理的问题中，扩展区间容易但收缩区间不好处理，这时可以考虑使用回滚莫队的技巧，以达到区间只增不减的效果。
具体步骤
- 对询问离线并排序，以左端点所在块号为第一关键字，右端点大小为第二关键字进行排序
- 以块号递增的顺序处理询问，每次只考虑左端点在该块内的询问
- 暴力回答所有左右端点都在块内的询问
- 记当前块号为 \(k\)，区间为 \([st[k],ed[k]]\)，考虑剩下的询问，显然询问的右端点都大于 \(ed[k]\) 并且递增
- 记当前已求得答案的区间为 \([l,r]\)，答案为 \(pre\)，若该询问是该块内的第一次询问则初始化区间为 \([l=ed[k]+1, r=ed[k]]\)
- 扩展 \(r\) 至当前询问的右边界，并更新答案 \(pre\)
- 建立临时变量 \(ans=pre\)，扩展 \(l\) 至当前询问的左边界，并更新答案 \(ans\)，扩展完毕后用 \(ans\) 回答当前询问
- 回撤左端点 \(l\) 至 \(ed[k]+1\)，并撤销扩展 \(l\) 时对辅助变量的更改，保留 \(pre\) 用于下次询问（即回撤区间至 \([ed[k],r]\)）
这样我们就实现了区间只增不减的莫队，步骤 8 中撤销左边界的具体实现视所用辅助变量而定，例如桶的话就 \(cnt[value]—\)，并查集的话用按秩合以支持撤销操作。
分析下复杂度，假定 \(n\) 和 \(m\) 同数量级，取块大小 \(B = \sqrt{n}\)，暴力处理块内询问 \(O(\sqrt{n})\)，每个块内右端点至多扩展 \(n\) 次 \(O(n\sqrt{n})\)，左端点每次最多扩展和撤销 \(\sqrt{n}\) 次，因此总复杂度仍为 \(O(n\sqrt{n})\)。
模板
扩展右端点：cnt[x]++,pre=max(pre,cnt[x]*x)
扩展右端点：cnt[x]++,ans=max(ans,cnt[x]*x)
回撤左端点：cnt[x]--
const int SZ = sqrt(MAXN);
vector<int> X;
int n,m,z;
int a[MAXN],b[MAXN],cnt[MAXN],id[MAXN],st[MAXN],ed[MAXN],t[MAXN];
struct query
{
int l,r,i; LL ans;
bool operator <(const query &t)const
{
if(id[t.l]!=id[l])return id[l]<id[t.l];
return r<t.r;
}
}q[MAXN];
inline LL baoli(int l,int r)
{
LL ans=0;
fp(i,l,r)t[b[i]]++,ans=max(ans,1LL*t[b[i]]*a[i]);
fp(i,l,r)t[b[i]]--;
return ans;
}
int work()
{
scanf("%d%d",&n,&m);
fp(i,1,n)scanf("%d",&a[i]),X.pb(a[i]);
fp(i,1,n)id[i]=(i-1)/SZ+1; z=id[n];
fp(i,1,n)if(!st[id[i]])st[id[i]]=i;
fd(i,n,1)if(!ed[id[i]])ed[id[i]]=i;
sort(all(X)),unq(X);
fp(i,1,n)b[i]=lb(all(X),a[i])-X.begin()+1;
fp(i,1,m)scanf("%d%d",&q[i].l,&q[i].r),q[i].i=i;
sort(q+1,q+1+m);
LL ans=0,pre=0;
for(int i=1,l,r;i<=m;i++)
{
int k=id[q[i].l];
if(id[q[i].l]!=id[q[i-1].l])mst(cnt,0),ans=pre=0,r=ed[k],l=ed[k]+1;
if(id[q[i].l]==id[q[i].r])q[i].ans=baoli(q[i].l,q[i].r);
else
{
while(l<=ed[k])cnt[b[l]]--,l++;
while(r<q[i].r)r++,cnt[b[r]]++,pre=max(pre,1LL*cnt[b[r]]*a[r]);
ans=pre;
while(l>q[i].l)l--,cnt[b[l]]++,ans=max(ans,1LL*cnt[b[l]]*a[l]);
q[i].ans=ans;
}
}
sort(q+1,q+1+m,[](const query &a,const query &b){return a.i<b.i;});
fp(i,1,m)printf("%lld\n",q[i].ans);
return 0;
}练习
Luogu P5906 【模板】回滚莫队&不删除莫队
扩展右端点再更新答案的同时记录每个数的最右出现位置，扩展左端点时用区间内最靠右的位置更新答案。
const int SZ = sqrt(MAXN);
int n,m;
int a[MAXN],t[MAXN],s1[MAXN],s2[MAXN];
int id[MAXN],st[MAXN],ed[MAXN];
struct query{int l,r,i,ans;}q[MAXN];
vector<int> X;
int baoli(int l,int r)
{
int ans=0;
fp(i,l,r)
if(!t[a[i]]) t[a[i]]=i;
else ans=max(ans,i-t[a[i]]);
fp(i,l,r)t[a[i]]=0;
return ans;
}
int work()
{
scanf("%d",&n);
fp(i,1,n)scanf("%d",&a[i]),X.pb(a[i]);
fp(i,1,n)id[i]=(i-1)/SZ+1;
fp(i,1,n)if(!st[id[i]])st[id[i]]=i;
fd(i,n,1)if(!ed[id[i]])ed[id[i]]=i;
sort(all(X)),unq(X);
fp(i,1,n)a[i]=lb(all(X),a[i])-X.begin()+1;
scanf("%d",&m);
fp(i,1,m)scanf("%d%d",&q[i].l,&q[i].r),q[i].i=i;
sort(q+1,q+1+m,[](const query &a,const query &b)
{
if(id[a.l]!=id[b.l])return id[a.l]<id[b.l];
return a.r<b.r;
});
int pre=0,ans=0,l,r;
fp(i,1,m)
{
int k=id[q[i].l];
if(id[q[i].l]!=id[q[i-1].l])
{
r=ed[k],l=ed[k]+1,ans=pre=0,mst(s1,0),mst(s2,0);
}
if(id[q[i].l]==id[q[i].r])q[i].ans=baoli(q[i].l,q[i].r);
else
{
while(r<q[i].r)
{
r++,s2[a[r]]=r;
if(!s1[a[r]])s1[a[r]]=r;
else pre=max(pre,r-s1[a[r]]);
}
ans=pre;
while(l>q[i].l)
{
l--;
if(!t[a[l]])t[a[l]]=l;
else ans=max(ans,t[a[l]]-l);
if(s2[a[l]])ans=max(ans,s2[a[l]]-l);
}
while(l<=ed[k])t[a[l]]=0,l++;
q[i].ans=ans;
}
}
sort(q+1,q+1+m,[](const query &a,const query &b){return a.i<b.i;});
fp(i,1,m)printf("%d\n",q[i].ans);
return 0;
}ICPC2017北京C
显然扩展区间时用并查集可以很简单的维护答案，实现并查集撤销后应用回滚莫队即可
这题有点玄学，理论上来说应该按度数分块，因为扩展区间的复杂度并不是 \(O(1)\) 的，而是取决于该点向区间内的连边数。那么应该保证块内总度数在 \(\sqrt{m}\) 的数量级内。。。但这么分块会 TLE，估计数据的连边都是随机的，每个块内的边数都在 \(\sqrt{n}\) 左右吧。
const int B = sqrt(50000);
struct dsu
{
struct info{int fa,sz;}t[MAXN];
vector<pair<int,info>> v;
void init(int n)
{
fp(i,1,n)t[i]={i,1};
v.clear();
}
int find(int x){return t[x].fa==x?x:find(t[x].fa);}
LL merge(int a,int b)
{
int fa=find(a),fb=find(b); LL ans=0;
v.pb({fa,t[fa]});
v.pb({fb,t[fb]});
if(fa!=fb)
{
if(t[fa].sz>t[fb].sz)swap(fa,fb);
ans=1LL*t[fa].sz*t[fb].sz;
t[fa].fa=fb;
t[fb].sz+=t[fa].sz;
}
return ans;
}
void undo()
{
t[v.back().fi]=v.back().se,v.ppb();
t[v.back().fi]=v.back().se,v.ppb();
}
}S,T;
int n,m,q;
int id[MAXN],st[MAXN],ed[MAXN];
vector<int> G[MAXN];
struct edge{int u,v;}e[MAXN];
struct query{int l,r;LL ans;int i;}a[MAXN];
void add(int i,int l,int r,dsu &d,LL &ans,int &cnt)
{
auto it = lb(all(G[i]),l), ed = ub(all(G[i]),r);
for(;it!=ed;it++)
{
int j=*it;
ans+=d.merge(i,j);
cnt++;
}
}
LL baoli(int l,int r)
{
int cnt=0; LL ans=0;
fp(i,l,r)add(i,l,r,T,ans,cnt);
while(cnt--)T.undo();
return ans;
}
int work()
{
MC
{
scanf("%d%d%d",&n,&m,&q);
S.init(n),T.init(n);
fp(i,1,n)G[i].clear();
fp(i,1,n)id[i]=(i-1)/B+1,st[id[i]]=ed[id[i]]=0;
fp(i,1,n)if(!st[id[i]])st[id[i]]=i;
fd(i,n,1)if(!ed[id[i]])ed[id[i]]=i;
fp(i,1,m)scanf("%d%d",&e[i].u,&e[i].v);
fp(i,1,q)scanf("%d%d",&a[i].l,&a[i].r),a[i].i=i;
sort(a+1,a+1+q,[](const query &a,const query &b)
{
if(id[a.l]!=id[b.l])return id[a.l]<id[b.l];
return a.r<b.r;
});
fp(i,1,m)G[e[i].u].pb(e[i].v),G[e[i].v].pb(e[i].u);
fp(i,1,n)sort(all(G[i]));
int l,r; LL ans=0,pre=0;
fp(i,1,q)
{
int k=id[a[i].l];
if(id[a[i].l]!=id[a[i-1].l])S.init(n),ans=pre=0,r=ed[k],l=ed[k]+1;
if(id[a[i].l]==id[a[i].r])a[i].ans=baoli(a[i].l,a[i].r);
else
{
int cnt=0;
while(r<a[i].r)r++,add(r,l,r,S,pre,cnt);
cnt=0,ans=pre;
while(l>a[i].l)l--,add(l,l,r,S,ans,cnt);
a[i].ans=ans,l=ed[k]+1;
while(cnt--)S.undo();
}
}
fp(i,1,n)G[i].clear();
sort(a+1,a+1+q,[](const query &a,const query &b)
{
return a.i<b.i;
});
fp(i,1,q)printf("%lld\n",a[i].ans);
}
return 0;
}