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

whiteqwq · 2020-06-20 21:53:10 · 题解

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;
}