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

· · 题解

呜呼呼这个回滚莫队大概是一种正难则反的思路，如果遇到比较毒瘤的删除的话，要不就减少删除的次数，要不就把删除改成插入

恰好这道题都用了，虽然套一个数据结构的莫队比较好做（可惜有个log），可是这道题已经写了【模板】回滚莫队&不删除莫队，所以我们至少得用莫队

首先一看就知道用st,ed两个桶，每次都记录这个点在[l,r](表示当前问题的左端点和右端点的位置)。

但是如果套普通的套一个莫队，你会发现这东西可以做到O(1)修改，但是似做不到O(1)撤销（除非开大空间存下来）

原来的莫队是左端点在每\sqrt{m}区间内的问题排序,所以这些询问的左端点都在一个块内部，右端点则是按r升序排序（不管奇偶性优化），可见对右端点可以做到没有删除操作，但是左端点则不然，况且左端点只有\sqrt{m}个操作，我们对左端点也可以做到没有插入操作，那就是每次从这个块的最右边往左移，每次向左之后要还原就行了。

可以看见每个块内的询问最多向右\sqrt{m}次

每个询问最多向左走\sqrt{m}次

复杂度还是O(n\sqrt{m})

除此之外本题还有一些细节要注意，写在代码注释上了

#include<touwenjian.h>

using namespace std;

const int maxn=502000;//用不到这么多的空间

int n,m;
int st[maxn],ed[maxn],looker[maxn],lok[maxn],a[maxn],b[maxn];
int ans;
int bj[maxn];
int len,cnt;
int aans[maxn];

struct que{
    int l,r,bh;
}q[maxn];

int cmp(que aa,que bb)
{
    if((aa.l-1)/len==(bb.l-1)/len) return aa.r<bb.r;
    return aa.l<bb.l;
}

int tst[maxn],ted[maxn],tlooker[maxn],tcnt;

int bl(int l,int r) //这东西得单独开一套变量来
{
    int i,ans=0;
    for(i=l;i<=r;i++)
    {
        if(!tst[a[i]]) tst[a[i]]=i;
        ted[a[i]]=max(ted[a[i]],i); ans=max(ted[a[i]]-tst[a[i]],ans); tlooker[++tcnt]=a[i]; 
    }
    for(i=1;i<=tcnt;i++) tst[tlooker[i]]=ted[tlooker[i]]=0,tlooker[i]=0;
    tcnt=0;
    return ans;
}

inline void addr(int x)  //右端点只有插入，因此可以保留
{
    if(!st[a[x]]) st[a[x]]=x; 
    ed[a[x]]=max(ed[a[x]],x); ans=max(ed[a[x]]-st[a[x]],ans); looker[++cnt]=a[x];
}

inline void addl(int x) //左端点每次都要清空，除了判断答案在左边这个块的情况暂时用一用ed数组（之后也要清空），其他都不能动。
{
    if(!ed[a[x]]) ed[a[x]]=x;
    else ans=max(ans,ed[a[x]]-x);
}

int main()
{
    ios::sync_with_stdio(false);
    register int i,j;
    cin>>n;
    len=sqrt(n);
    for(i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
    sort(b+1,b+n+1); int tot=unique(b+1,b+n+1)-b-1;
    for(i=1;i<=n;i++) a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
    cin>>m;
    for(i=1;i<=m;i++) cin>>q[i].l>>q[i].r,q[i].bh=i;
    sort(q+1,q+m+1,cmp);
    i=1;
    for(j=1;j<=(n-1)/len+1;j++)
    {
        ans=0;
        int baspla=min(len*j,n);
        int l=baspla+1,r=baspla;
        for(;(q[i].l-1)/len+1==j&&i<=m;i++) //一定要加上i<=m的判断
        {
            if((q[i].l-1)/len==(q[i].r-1)/len) aans[q[i].bh]=bl(q[i].l,q[i].r);
            else
            {
                while(q[i].r>r) addr(++r); //莫队基本操作
                int rigans=ans;
                while(q[i].l<l) addl(--l);
                while(l<=baspla) { if(ed[a[l]]<=baspla) ed[a[l]]=0; l++;}
                aans[q[i].bh]=ans; 
                ans=rigans;
            }
        }
        for(int k=1;k<=cnt;k++) st[looker[k]]=ed[looker[k]]=0,looker[k]=0;
        //记得清空
        cnt=0;
    }
    for(i=1;i<=m;i++) cout<<aans[i]<<endl;
    return 0;
}