题解 P5906 【【模板】回滚莫队】

· · 题解

感觉并不用特意去卡常啊，只要不滥用memset就能轻松地跑很快了

还有话说虽然这是道模板题，但我觉得AT1219 歴史の研究可能才是更多人的回滚莫队模板题

题解：

传统莫队众所周知有两个操作：增和减

增的操作一般情况下都是好做的，但减就不一定了

例如本题，想要删最左边界的话，就要知道次左边界，然后又依次类推，这就不是“优雅的暴力”了

而回滚莫队就是解决这种问题的利器，大致思想是利用更多的增操作代替减操作

也就是我们现在要构造出一种方案，复杂度有保障的情况下，使得l指针和r指针都能（尽量）一直往自己的正方向走

r指针很好解决，排序时将询问的r边界按从小到大排就好了

l指针呢，运用分块的思想我们可以将l边界在同一块中的询问排序排在一起以便一起处理，具体的处理方法就是不断地将l指针拉回块的右边界，拉到询问的位置，拉回块的右边界，拉到询问的位置。。。

稍微总结一下：分块莫队就是将左边界在同一块中的询问放在一起处理，r指针可以通过排序实现单调移动，而l指针可以不断地拉回当前块的右边，再对于每个询问单调地向左移动（脑补反复横跳），由于块的大小是根号的，因此对于一次询问，l指针的移动始终不会超过根号次。另外有些询问可能左右边界是在同一块中的，这时我们就可以暴力遍历一遍，反正长度不会超过根号嘛

让我们来看下这道题的具体情况：

我们记左指针为l，右指针为r，当前块的右边界（分界线）为mid，[l,mid]为左区间，[mid,r]为右区间

然后答案会有三种情况出现：

  1. 答案完全在左区间中

  2. 答案完全在右区间中

  3. 答案一部分在左区间中，一部分在右区间中

注意到答案的右端点是单调的，因此取个max即可，与当前扫到的下标减一减就解决了情况1和3

对于情况2，我们要额外记录一个值，记录一个数在右区间中第一次出现的位置

假如max也在右区间中，减一减，就得到了情况2的答案

然后简单讲一下清空桶的方法

用暴力的memset肯定是不优秀的，因为有许多冗余操作（他都没赋过值，你为啥要清空？），为了避免这些冗余，我们可以开个数组记录下我们曾经对哪些桶做过修改，最后在遍历下这个数组将那些曾经被修改过的桶赋回0就好了，而记录数组的清空只要O(1)就好了

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int N=2e5+5;
int un,n,m,a[N],ANS[N],ma[N],b[N],bn,num[N],st[N],cn,clear[N];
//变量的解释下面的代码中都有哦！！！
struct que{
    int l,r,i;
    inline bool operator < (const que &nt) const {
        return (b[l]^b[nt.l])?b[l]<b[nt.l]:r<nt.r; //先按左边界所在块排，相同时再按右边界排
    }
}q[N];

inline int max(const int &x,const int &y){
    return x>y?x:y;
}

int calc(int l,int r){ //暴力扫一遍
    int last[N],res=0;
    for(int i=l;i<=r;i++) last[a[i]]=0; //记录每个数最早出现的位置
    for(int i=l;i<=r;i++) if(!last[a[i]]) last[a[i]]=i; else res=max(res,i-last[a[i]]);
    return res;
}

signed main(){
    read(n);
    int len=sqrt(n); //块长
    for(int i=1;i<=n;i++) num[i]=read(a[i]),b[i]=(i-1)/len+1; //b记录每个下标是在哪个块中的
    bn=b[n]; //块数
    sort(num+1,num+1+n);
    un=unique(num+1,num+1+n)-num-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(num+1,num+1+un,a[i])-num; //正常的离散操作
    read(m);
    for(int i=1;i<=m;i++){
        read(q[i].l);read(q[i].r);
        q[i].i=i;
    }
    sort(q+1,q+1+m); //询问排序
    for(int i=1,j=1;j<=bn;j++){ //i枚举询问,j枚举询问的左边界所在块
        int br=min(n,j*len),l=br+1,r=l-1,ans=0; //br是当前块的右边界
        cn=0; //清空记录数组的指针
        for(;b[q[i].l]==j;i++){ //枚举当前块内的询问
            if(b[q[i].r]==j){ //如果左右边界都在同一块内内就暴力做
                ANS[q[i].i]=calc(q[i].l,q[i].r);
                continue;
            }
            while(r<q[i].r){
                r++;
                ma[a[r]]=r; //最后出现的位置
                if(!st[a[r]]) st[a[r]]=r,clear[++cn]=a[r]; //st是最早出现的位置，clear是出现过的数字，用来清空数字最后出现的位置
                ans=max(ans,r-st[a[r]]); //情况2
            }
            int tp=ans; //先保存一下，因为右区间的贡献不会被刷新，但左区间的会
            while(l>q[i].l){
                l--;
                if(ma[a[l]]) ans=max(ans,ma[a[l]]-l);
                else ma[a[l]]=l; //最后出现的位置可能在左区间中
            }
            ANS[q[i].i]=ans;
            while(l<=br){
                if(ma[a[l]]==l) ma[a[l]]=0; //去掉左区间的贡献
                l++;
            }
            ans=tp; //去掉当前左区间的贡献
        }
        for(int i=1;i<=cn;i++) ma[clear[i]]=st[clear[i]]=0; //根据记录数组清空每个数出现位置的各种信息
    }
    for(int i=1;i<=m;i++) write(ANS[i]),puts("");
}