对于一些区间问题，虽然莫队好进行加操作，但并不好进行减操作，所以我们引出了回滚莫队。
【模板】回滚莫队&不删除莫队
发现我们并不总是知道什么时候取哪些值为最大值，尤其是删操作时，回滚莫队就是只用加操作实现的。
我们对询问左端点所在的块排序，相同的话按照右排序，这样对于相同的左端点的块，右端点总是单调不降的，总是加操作地向右拓展，对于左端点的块，每次向左进行加操作，结束后都回到左端点所在的块的右边界并将所有标记复原。
左右端点在同一个块内就可以直接暴力查询。
可以发现复杂度始终都是对的。
#include <bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1
#define re register
#define pb push_back
#define pir pair<int,int>
#define f1(x) for(int i=1;i<=x;i++)
#define f0(x) for(int i=0;i<=x;i++)
#define fr1(x) for(int i=x;i>=1;i--)
#define fr0(x) for(int i=x;i>=0;i--)
const int N=2e5+10,M=25005;
const int mod=1e9+7;
using namespace std;
int n,m;
int a[N],b[N];
int of[N],len;
int ans[N];
struct ss{
int l,r,id;
}q[N];
bool cmp(ss g,ss h){
return (of[g.l]^of[h.l])?of[g.l]<of[h.l]:g.r<h.r;
}
int baoli(int l,int r){
int vis[N],sum=0;
for(int i=l;i<=r;i++){
vis[a[i]]=0;
}
for(int i=l;i<=r;i++){
if(!vis[a[i]]){
vis[a[i]]=i;
}
else{
sum=max(sum,i-vis[a[i]]);
}
}
return sum;
}
int la[N],st[N],clea[N],cn;
signed main(){
// freopen("xp1.in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
len=sqrt(n);
f1(n){
cin>>a[i];
b[i]=a[i];
of[i]=(i-1)/len+1;
}
sort(b+1,b+1+n);
int tot=unique(b+1,b+1+n)-b-1;
f1(n){
a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
}
cin>>m;
f1(m){
cin>>q[i].l>>q[i].r;
q[i].id=i;
}
sort(q+1,q+m+1,cmp);
int bn=of[n];
for(int i=1,j=1;j<=bn;j++){//i询问数，j左边界所在块
int sum=0,cn=0,br=min(n,j*len),l=br+1,r=l-1;
for(;of[q[i].l]==j;i++){
if(of[q[i].r]==j){
ans[q[i].id]=baoli(q[i].l,q[i].r);
continue;
}
while(r<q[i].r){
r++;
la[a[r]]=r;
if(!st[a[r]]){
st[a[r]]=r;
clea[++cn]=a[r];
}
sum=max(sum,r-st[a[r]]);
}
int tp=sum;
while(l>q[i].l){
l--;
if(la[a[l]]){
sum=max(sum,la[a[l]]-l);
}
else{
la[a[l]]=l;
}
}
ans[q[i].id]=sum;
while(l<br+1){
if(la[a[r]]==l){
la[a[r]]=0;
}
l++;
}
sum=tp;
}
for(int k=1;k<=cn;k++){
la[clea[k]]=st[clea[k]]=0;
}
}
f1(m){
cout<<ans[i]<<"\n";
}
return 0;
}
歴史の研究
同样维护出现次数。
#include <bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1
#define re register
#define pb push_back
#define pir pair<int,int>
#define f1(x) for(int i=1;i<=x;i++)
#define f0(x) for(int i=0;i<=x;i++)
#define fr1(x) for(int i=x;i>=1;i--)
#define fr0(x) for(int i=x;i>=0;i--)
const int N=2e5+10,M=25005;
const int mod=1e9+7;
using namespace std;
int n,m;
int a[N],b[N];
int of[N],len;
int ans[N];
struct ss{
int l,r,id;
}q[N];
bool cmp(ss g,ss h){
return (of[g.l]^of[h.l])?of[g.l]<of[h.l]:g.r<h.r;
}
int baoli(int l,int r){
int vis[N],sum=0;
for(int i=l;i<=r;i++){
vis[a[i]]=0;
}
for(int i=l;i<=r;i++){
vis[a[i]]++;
sum=max(sum,vis[a[i]]*b[a[i]]);
}
return sum;
}
int la[N],st[N],clea[N],cn;
signed main(){
// freopen("xp1.in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
len=sqrt(n);
f1(n){
cin>>a[i];
b[i]=a[i];
of[i]=(i-1)/len+1;
}
sort(b+1,b+1+n);
int tot=unique(b+1,b+1+n)-b-1;
f1(n){
a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
}
f1(m){
cin>>q[i].l>>q[i].r;
q[i].id=i;
}
sort(q+1,q+m+1,cmp);
int bn=of[n];
for(int i=1,j=1;j<=bn;j++){//i询问数，j左边界所在块
int sum=0,cn=0,br=min(n,j*len),l=br+1,r=l-1;
for(;of[q[i].l]==j;i++){
if(of[q[i].r]==j){
ans[q[i].id]=baoli(q[i].l,q[i].r);
continue;
}
while(r<q[i].r){
r++;
la[a[r]]++;
clea[++cn]=a[r];
sum=max(sum,la[a[r]]*b[a[r]]);
}
int tp=sum;
while(l>q[i].l){
l--;
la[a[l]]++;
sum=max(sum,la[a[l]]*b[a[l]]);
}
ans[q[i].id]=sum;
while(l<br+1){
la[a[l]]--;
l++;
}
sum=tp;
}
for(int k=1;k<=cn;k++){
la[clea[k]]=0;
}
}
f1(m){
cout<<ans[i]<<"\n";
}
return 0;
}