P5906 【模板】回滚莫队&不删除莫队

解题报告

P5906 【模板】回滚莫队&不删除莫队解题报告：

更好的阅读体验

题意

题意：给定一个长为$n$的序列$a$，$m$次询问，求区间$[l,r]$内相同的数的最远间隔距离，注意这里的距离指下标差的绝对值。

数据范围：$1\leqslant n,m\leqslant 2\cdot 10^5$。

分析

这是一道回滚莫队的细节题（大部分OIer的回滚莫队入门题为AT1219 歴史の研究，所以在这里我就没有对回滚莫队的讲解了），肝了很久，如果不会回滚莫队的人可以跳过这篇题解。

在回滚莫队之前，我们可以看一下两个预处理
分块：

t=sqrt(n);
for(i=1;i<=t;i++)
    l[i]=r[i-1]+1,r[i]=i*t;
if(r[t]<n)
    t++,l[t]=r[t-1]+1,r[t]=n;
for(i=1;i<=t;i++)
    for(j=l[i];j<=r[i];j++)
        pos[j]=i;

注：这里$t$指块数，$l$指块的左边界，$r$指块的右边界，$pos$指当前位置所在的块。

离散化：

struct number{
    int pos,val;
}num[maxn];
inline int cmp1(number a,number b){
    return a.val<b.val;
}
for(i=1;i<=n;i++)
    scanf("%d",&num[i].val),num[i].pos=i;
sort(num+1,num+1+n,cmp1);
tot=0;
for(i=1;i<=n;i++){
    if(i==1||num[i-1].val!=num[i].val)
        tot++;
    a[num[i].pos]=tot;
}

这里的离散化我写的方法有点不一样，但意思很容易懂，就不赘述了（$num$是离散化的数组，$a$是离散化后的数组，$tot$是帮助离散化的计数器）。

然后是$\text{add}$函数，即暴力在区间中加入这个数，更新答案：

inline void add(int x){
    st[a[x]]=min(st[a[x]],x),ed[a[x]]=max(ed[a[x]],x);
    now=max(now,ed[a[x]]-st[a[x]]);
}

我们按照回滚莫队的板子，可以把莫队拆成四个部分：
1.在同一个块中的暴力：这个很容易写：

if(pos[qx]==pos[qy]){
    for(j=qx;j<=qy;j++)
        tmpst[a[j]]=inf,tmped[a[j]]=-inf;
    for(j=qx;j<=qy;j++){
        tmpst[a[j]]=min(tmpst[a[j]],j),tmped[a[j]]=max(tmped[a[j]],j);
        tmpn=max(tmpn,tmped[a[j]]-tmpst[a[j]]);
    }
    ans[qi]=tmpn;
    continue;
}

2.换块：这里的换块可以直接将空区间放在$r_{pos[x]}$的位置，即当前询问的左边界所在块的右边界，记得要把$st$数组置极大值，$ed$数组置极小值，因为换块操作只有$\sqrt{n}$次，因此暴力清零总体是$O(n\sqrt{n})$的（$st$记录每个数字在区间中开始的位置，$ed$记录结束的位置）。

if(pos[qx]!=lst){
    x=r[pos[qx]]+1,y=r[pos[qx]];
    now=0,lst=pos[qx];
    for(j=1;j<=tot;j++)
        st[j]=inf,ed[j]=-inf;
}

3.右区间扩张，很容易写出代码：

while(y<qy)
    y++,add(y);

4.记录当前的答案，更新当前区间答案，再用之前的答案覆盖当前的答案（$tmpst$和$tmped$是记录左右区间的数组，$tmpn$记录答案，$tmpx$记录之前的左区间），但是这个时间复杂度有点高，因为清零操作最劣$O(n)$，因此复杂度会高达$O(nm)$。

tmpn=now,tmpx=x;
for(j=qx;j<=qy;j++)
    tmpst[a[j]]=st[a[j]],tmped[a[j]]=ed[a[j]];
while(x>qx)
    x--,add(x);
ans[qi]=now,now=tmpn,x=tmpx;
for(j=qx;j<=qy;j++)
    st[a[j]]=tmpst[a[j]],ed[a[j]]=tmped[a[j]];

然后你就可以获得$15pts$的高分！

考虑优化，发现覆盖数组太麻烦了，直接在$tmpst$与$tmped$上修改可以省去一个循环（但只能优化一些常数）。

我们将上面的代码改为：

while(y<qy)
    y++,add(y);
tmpn=now,tmpx=x;
for(j=qx;j<=qy;j++)
    tmpst[a[j]]=st[a[j]],tmped[a[j]]=ed[a[j]];
while(x>qx)
    x--,tmpadd(x);
ans[qi]=now,now=tmpn,x=tmpx;

然后增加一个$\text{tmpadd}$函数：

inline void tmpadd(int x){
    tmpst[a[x]]=min(tmpst[a[x]],x),tmped[a[x]]=max(tmped[a[x]],x);
    now=max(now,tmped[a[x]]-tmpst[a[x]]);
}

分数：$65pts$。

我们发现时间复杂度的瓶颈还是在记录$tmpst$与$tmped$上，我们会记录很多不会修改到的信息，因此可以考虑一个小$trick$：时间戳+$vis$数组优化，这个优化可以适用于很多重置数组为时间复杂度瓶颈的题目。

具体操作：每次循环开始时$stp$加一（$stp$指时间戳），然后直接删去上面代码的循环置$tmpst$和$tmped$部分，继续修改$\text{tmpadd}$函数：

inline void tmpadd(int x){
    if(vis[a[x]]!=stp)
        vis[a[x]]=stp,tmpst[a[x]]=st[a[x]],tmped[a[x]]=ed[a[x]];
    tmpst[a[x]]=min(tmpst[a[x]],x),tmped[a[x]]=max(tmped[a[x]],x);
    now=max(now,tmped[a[x]]-tmpst[a[x]]);
}

大意就是如果这个点在当前时间戳还没有访问过，就给$tmpst$和$tmped$赋值，并记录$vis$数组，由于$x$每次回滚都会到当前块的右边界加一位置，因此$x$到$qx$的距离最多是$\sqrt{n}$，因此每次询问最多进行$\sqrt{n}$次$\text{tmpadd}$操作，这样$tmpst$和$tmped$的赋值就变为了$O(\sqrt{n})$，即整体赋值的复杂度降到了$O(m\sqrt{n})$。

总体复杂度$O(n\sqrt{n})$（这里默认$n,m$同阶，事实也如此），可以通过本题。

代码

#include<stdio.h>
#include<math.h>
#include<algorithm>
#define inf 1000000000
using namespace std;
const int maxn=200005,maxm=200005;
int i,j,k,m,n,t,tot,x,y,now,lst,stp;
int a[maxn],ans[maxm],l[maxn],r[maxn],pos[maxn],st[maxn],ed[maxn],tmpst[maxn],tmped[maxn],vis[maxn];
struct number{
    int pos,val;
}num[maxn];
struct question{
    int x,y,id;
}q[maxm];
inline int cmp1(number a,number b){
    return a.val<b.val;
}
inline int cmp2(question a,question b){
    return pos[a.x]^pos[b.x]? a.x<b.x:a.y<b.y; 
}
inline void add(int x){
    st[a[x]]=min(st[a[x]],x),ed[a[x]]=max(ed[a[x]],x);
    now=max(now,ed[a[x]]-st[a[x]]);
}
inline void tmpadd(int x){
    if(vis[a[x]]!=stp)
        vis[a[x]]=stp,tmpst[a[x]]=st[a[x]],tmped[a[x]]=ed[a[x]];
    tmpst[a[x]]=min(tmpst[a[x]],x),tmped[a[x]]=max(tmped[a[x]],x);
    now=max(now,tmped[a[x]]-tmpst[a[x]]);
}
int main(){
    scanf("%d",&n);
    t=sqrt(n);
    for(i=1;i<=t;i++)
        l[i]=r[i-1]+1,r[i]=i*t;
    if(r[t]<n)
        t++,l[t]=r[t-1]+1,r[t]=n;
    for(i=1;i<=t;i++)
        for(j=l[i];j<=r[i];j++)
            pos[j]=i;
    for(i=1;i<=n;i++)
        scanf("%d",&num[i].val),num[i].pos=i;
    sort(num+1,num+1+n,cmp1);
    tot=0;
    for(i=1;i<=n;i++){
        if(i==1||num[i-1].val!=num[i].val)
            tot++;
        a[num[i].pos]=tot;
    }
    scanf("%d",&m);
    for(i=1;i<=m;i++)
        scanf("%d%d",&q[i].x,&q[i].y),q[i].id=i;
    sort(q+1,q+1+m,cmp2);
    x=1,y=0,now=0,lst=0;
    for(i=1;i<=m;i++){
        stp++;
        int qx=q[i].x,qy=q[i].y,qi=q[i].id,tmpn=0,tmpx;
        if(pos[qx]==pos[qy]){
            for(j=qx;j<=qy;j++)
                tmpst[a[j]]=inf,tmped[a[j]]=-inf;
            for(j=qx;j<=qy;j++){
                tmpst[a[j]]=min(tmpst[a[j]],j),tmped[a[j]]=max(tmped[a[j]],j);
                tmpn=max(tmpn,tmped[a[j]]-tmpst[a[j]]);
            }
            ans[qi]=tmpn;
            continue;
        }
        if(pos[qx]!=lst){
            x=r[pos[qx]]+1,y=r[pos[qx]];
            now=0,lst=pos[qx];
            for(j=1;j<=tot;j++)
                st[j]=inf,ed[j]=-inf;
        }
        while(y<qy)
            y++,add(y);
        tmpn=now,tmpx=x;
        while(x>qx)
            x--,tmpadd(x);
        ans[qi]=now,now=tmpn,x=tmpx;
    }
    for(i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}