前置知识
之前写的普通莫队笔记，在这里当个前置知识，其实大约知道莫队大概就是把询问离线下来，分块并排序之后用两个指针 \(l,r\) 来更新信息统计答案即可。
有时在区间转移的时候，有些删除或添加的操作无法实现，那么当只有一种操作不能实现的时候，就可以用莫队来解决这个问题，然而普通莫队是很难解决（或者说是不能解决）这个问题的，所以我们要对普通莫队进行改造，也就是回滚莫队。
本文出现所有代码缺省源使用V5.3.
「例题一」洛谷模板
原题链接：P5906 【模板】回滚莫队&不删除莫队。
「例题一」题目简述
给定一个序列，多次询问一段区间 \([l,r]\)，求区间中相同的数的最远间隔距离。
序列中两个元素的间隔距离指的是两个元素下标差的绝对值。
「例题一」思路简述
首先来说这个题有什么操作不能实现。显然增加是好实现的，只需要每次在增加时更新距离信息（记录第一次出现和最后一次出现）即可。但是删除操作不能这样实现，因为在删除的时候若要更新答案，需要知道次大值……肯定是不能这样维护的，所以我们要让 \(l\) 和 \(r\) 在移动的过程中尽量避免删除操作，也就是尽量让 \(l\) 向左端移动，\(r\) 向右端移动。
那么我们每次枚举块，把块内的询问解决的时候，每次把 \(l\) 拉回当前块的右端，然后保证 \(r\) 只向右端移动，\(l\) 不断根据询问反复横跳，对于在一个块内的询问暴力更新（复杂度 \(O(\sqrt{n})\)，不过可能实际略大），否则跳两个指针更新答案。因为块的是 \(O(\sqrt{n})\) 的，所以对于每个询问，\(l\) 的移动是 \(O(\sqrt{n})\) 的，所以这样做的复杂度就是 \(O(n\sqrt{m}).\)
「例题一」Code
template<typename J>
I J Hmax(const J &x,const J &y) {
Heriko x>y?x:y;
}
template<typename J>
I J Hmin(const J &x,const J &y) {
Heriko x<y?x:y;
}
CI MXX(2e5+1);
int ans[MXX],a[MXX],b[MXX],n,blo[MXX],len,blocnt,qn,appeared[MXX],fstpos[MXX],lstpos[MXX],apn;
struct Query {
int l,r,id;
I bool operator < (const Query &co) const {
Heriko (blo[l]==blo[co.l])?(r<co.r):(blo[l]<blo[co.l]);
}
}
q[MXX];
int lst[MXX];
I int Clac_Faster_Than_SF1000(int l,int r) {
int res(0);
for(int i(l);i<=r;++i)
lst[a[i]]=0;
for(int i(l);i<=r;++i)
if(!lst[a[i]])
lst[a[i]]=i;
else
res=Hmax(res,i-lst[a[i]]);
Heriko res;
}
S main() {
Files();
fr(n),len=sqrt(n);
for(int i(1);i<=n;++i)
fr(a[i]),b[i]=a[i];
sort(b+1,b+1+n);
int nl(unique(b+1,b+1+n)-b-1);
for(int i(1);i<=n;++i)
a[i]=lower_bound(b+1,b+1+nl,a[i])-b;
for(int i(1);i<=n;++i)
blo[i]=(i-1)/len+1;
blocnt=blo[n];
fr(qn);
for(int i(1);i<=qn;++i)
fr(q[i].l),fr(q[i].r),q[i].id=i;
sort(q+1,q+1+qn);
int l(0),r(0),nw(1),tmpans(0);
for(int i(1);i<=blocnt;++i) {
int rx(Hmin(n,i*len));
l=rx+1,r=rx,tmpans=0,apn=0;
for(;blo[q[nw].l]==i;++nw) {
if(blo[q[nw].r]==i)
ans[q[nw].id]=Clac_Faster_Than_SF1000(q[nw].l,q[nw].r);
else {
while(r<q[nw].r) {
++r;
lstpos[a[r]]=r;
if(!fstpos[a[r]])
fstpos[a[r]]=r,appeared[++apn]=a[r];
tmpans=Hmax(tmpans,r-fstpos[a[r]]);
}
int lsttmp(tmpans);
while(l>q[nw].l) {
--l;
if(lstpos[a[l]])
tmpans=Hmax(tmpans,lstpos[a[l]]-l);
else
lstpos[a[l]]=l;
}
ans[q[nw].id]=tmpans;
while(l<=rx) {
if(lstpos[a[l]]==l)
lstpos[a[l]]=0;
++l;
}
tmpans=lsttmp;
}
}
for(int i(1);i<=apn;++i)
fstpos[appeared[i]]=lstpos[appeared[i]]=0;
}
for(int i(1);i<=qn;++i)
fw(ans[i],1);
Heriko Deltana;
}
「例题二」AT1219 歴史の研究
原题链接：AtCoder-JOI2014 歴史の研究；
洛谷链接：AT1219 歴史の研究。
「例题二」题目简述
给出长度为 \(N\) 的序列，\(Q\) 次询问，每次询问区间 \([L,R]\) 中最大的重要度。
重要度的定义为当前事件的权值 \(X_i\) 乘上事件在区间中出现次数 \(T_i.\)
「例题二」思路简述
和上个题一样，这个题添加操作也是很好实现的，维护一个桶即可，删除操作一样的不能实现，所以我们用同样的策略。
「例题二」Code
template<typename J>
I J Hmax(const J &x,const J &y) {
Heriko x>y?x:y;
}
template<typename J>
I J Hmin(const J &x,const J &y) {
Heriko x<y?x:y;
}
CI MXX(2e5+1);
int a[MXX],b[MXX],lx[MXX],rx[MXX],blo[MXX],n,qn,len,blocnt,cnt[MXX],co[MXX];
LL ans[MXX],tmpans;
struct Query {
int l,r,id;
I bool operator < (const Query &co) const {
Heriko blo[l]==blo[co.l]?r<co.r:l<co.l;
}
}
q[MXX];
I void Add(int x) {
++cnt[a[x]];
tmpans=Hmax(tmpans,(LL)cnt[a[x]]*b[a[x]]);
}
S main() {
Files();
fr(n),fr(qn),len=sqrt(n),blocnt=n/len;
for(int i(1);i<=n;++i)
fr(a[i]),b[i]=a[i];
for(int i(1);i<=qn;++i)
fr(q[i].l),fr(q[i].r),q[i].id=i;
sort(b+1,b+1+n);
int nl(unique(b+1,b+1+n)-b-1);
for(int i(1);i<=n;++i)
a[i]=lower_bound(b+1,b+1+nl,a[i])-b;
for(int i(1);i<=n;++i)
blo[i]=(i-1)/len+1;
for(int i(1);i<=blocnt;++i)
lx[i]=rx[i-1]+1,rx[i]=lx[i]+len-1;
if(rx[blocnt]<n)
++blocnt,lx[blocnt]=rx[blocnt-1]+1,rx[blocnt]=n;//这里用了一种和前面不同的处理每个块端点的方法，都不难写
int l(0),r(0),nw(1);
sort(q+1,q+1+qn);
for(int i(1);i<=blocnt;++i) {
mst(cnt,0);
r=rx[i],tmpans=0;
while(blo[q[nw].l]==i) {
l=rx[i]+1;
if(q[nw].r-q[nw].l<=len) {
mst(co,0);
LL anothertmpans(0);
for(int i(q[nw].l);i<=q[nw].r;++i)
++co[a[i]];
for(int i(q[nw].l);i<=q[nw].r;++i)
anothertmpans=Hmax(anothertmpans,(LL)co[a[i]]*b[a[i]]);
for(int i(q[nw].l);i<=q[nw].r;++i)
--co[a[i]];
ans[q[nw].id]=anothertmpans;
}
else {
while(q[nw].r>r)
Add(++r);
LL lsttmp(tmpans);
while(q[nw].l<l)
Add(--l);
ans[q[nw].id]=tmpans;
tmpans=lsttmp;
while(l<=rx[i])
--cnt[a[l++]];
}
++nw;
}
}
for(int i(1);i<=qn;++i)
fw(ans[i],1);
Heriko Deltana;
}
终了
终了。