回滚莫队&不删除莫队

模板链接

---

关于回滚莫队

你需要先学会莫队,我们做静态区间问题时有时候会遇到这种情况

给你一个序列，你需要维护序列的某个东西，但是对于这个东西，每次加入很好维护，但删除很难维护

那么我们就需要用到回滚莫队了

具体实现

1. 将序列以左端点的块的下标为第一关键词，右端点的下标为第二关键词排序（注意不要用莫队的奇偶排序优化）
2. 排序后，对于询问 $[ql,qr]$ 如果 $block[ql]=block[qr] $ 那么我们直接暴力枚举从 $l$ 到 $r$,时间复杂度为$O(\sqrt n)$
3. 如果 $l$ 移动到了下一个块，我们对 $l,r$ 进行初始化，将 $l$ 转移为 $R[block[l]]+1$ ,将 $r$ 转移为 $R[block[r]]$
4. 我们先将 $r$ 右移至 $qr$ 并加入期间每一个数，再将 $l$ 左移至 $ql$ 并加入
5. 最后再将 $l$ 回滚回初始化时的位置
6. 显而易见，复杂度为$O(m\sqrt n)$

关于本题

在本题中，我们需要记录的是两个值相同的点的最远距离，那么这个答案区间总共有三种情况:

1. 全在右区间
2. 全在左区间
3. 横跨中点(初始化时的 $l$ )

对于 2,3 两种情况，我们只需要对于每个值记录一个最大下标，再每次相减即可；而对于第 1 种情况，我们则单独记录一个右区间最小下标即可

一些细节

对于每次回滚/初始化，我们不用memset清空数组(事实上这样会超时)，而是直接在移动时判断当前点是否为最大/最小下标来进行清空
$$
\large\color{grey}{\text{Talk is cheap , show you the code}}
$$

#include<touwenjian.h>
using namespace std;
typedef long long ll;
const int maxn=200005;
const int inf=0x3f3f3f3f;
int n,m,a[maxn],b[maxn];
int block[maxn],R[maxn];
int ans[maxn],ma[maxn],mi[maxn];
struct question
{
    int l,r,id;
}q[maxn];

inline void read(int &num)
{
    int sign=1;
    char c;
    while((c=getchar())<'0'||c>'9')
        if(c=='-')sign=-1;
    num=c-'0';
    while((c=getchar())>='0'&&c<='9')
        num=(num<<1)+(num<<3)+c-'0';
    num*=sign;
}

bool cmp(const question &x,const question &y)
{
    return block[x.l]^block[y.l]?block[x.l]<block[y.l]:x.r<y.r;
}

signed main(void)
{
    freopen("text.in","r",stdin);
    read(n);
    for(register int i=1;i<=n;++i)read(a[i]),b[i]=a[i];
    sort(b+1,b+1+n);
    int M=unique(b+1,b+1+n)-b-1;
    for(register int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+1+M,a[i])-b;
    int len=sqrt(n);
    for(register int i=1;i<=n;++i)block[i]=(i-1)/len+1;
    for(register int i=1;i<=len+1;++i)R[i]=min(i*len,n);
    read(m);
    for(register int i=1;i<=m;++i)read(q[i].l),read(q[i].r),q[i].id=i;
    sort(q+1,q+1+m,cmp);
    int l=0,r=0,lastblock=0;
    int temp;
    for(register int i=1;i<=m;++i)
    {
        if(block[q[i].l]==block[q[i].r])
        {
            temp=0;
            for(register int j=q[i].r;j>=q[i].l;--j)ma[a[j]]=0;
            for(register int j=q[i].r;j>=q[i].l;--j)
                if(!ma[a[j]])ma[a[j]]=j;
                else temp=max(temp,ma[a[j]]-j);
            for(register int j=q[i].r;j>=q[i].l;--j)ma[a[j]]=0;
            ans[q[i].id]=temp;
            continue;
        }
        if(lastblock^block[q[i].l])
        {
            while(r>R[block[q[i].l]])
            {
                ma[a[r]]=0,mi[a[r]]=0;
                --r;
            }
            while(l<R[block[q[i].l]]+1)
            {
                ma[a[l]]=0,mi[a[l]]=0;
                ++l;
            }
            r=l-1;
            lastblock=block[q[i].l];
            temp=0;
        }
        while(r<q[i].r)
        {
            ++r;
            if(!mi[a[r]])mi[a[r]]=r,ma[a[r]]=r;
            else ma[a[r]]=r,temp=max(temp,r-mi[a[r]]);
        }
        int _l=l,res=temp;
        while(_l>q[i].l)
        {
            --_l;
            if(!ma[a[_l]])ma[a[_l]]=_l;
            else res=max(res,ma[a[_l]]-_l);
        }
        ans[q[i].id]=res;
        while(_l<l)
        {
            if(ma[a[_l]]==_l)ma[a[_l]]=0;
            ++_l;
        }
    }
    for(register int i=1;i<=m;++i)printf("%d\n",ans[i]);
    return 0;
}