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

· · 题解

题目传送门

题意

Sol

回滚莫队

显然，由名字得，回滚莫队还是要用莫队的基本思想。

这里不再赘述普通莫队的解决方案。

这种方式主要用于可离线查询，其中插入删除操作中一种方便一种复杂甚至不可做的情况。

既然一种简单一种麻烦，我们肯定选用简单的好qwq。

那么我们尽量全用简单的。

以下内容默认插入操作简单，反之类似。

排序方式与原先类似。

第一关键字 左端点所在块，第二关键字 右端点递增。

这样当左端点在同一块中，我们已经保证了右端点只有插入操作。

那么对于左端点，我们可以采取一个很暴力的操作——每次操作完回滚至当前块右端点，即从块右端点扩展到询问左端点，再将左端点还原回块右端点。

这是回滚莫队的核心操作。

当然我们还要考虑询问右端点在左端点同一块内的情况。

这种情况直接暴力跑即可，复杂度与拓展相同。

这样一次暴力时间复杂度是 O(\sqrt n \times k) （k 是一次增量所需时间）

同样对于莫队拓展我们知道是 O(n\sqrt n \times k)

若 n 次暴力也相等。

所以回滚莫队复杂度即 O(n\sqrt n\times k)

对于本题，每次跑完一组块时，你还要清除痕迹。

建议拿一个东西记录已使用的位置，每次只需清理这些即可。

可以减小常数。

代码。

/*
***
还要继续努力
成为一名烤咕学家哦
***
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,m,a[N],len,l,r,sum,vst[N],cnt,ans[N],lst[N],nxt[N],lsh[N],qaq,qwq;
struct Question{int l,r,id,pos;}q[N];
template <typename T> void rd(T &x){
    int fl=1;x=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fl=-fl;
    for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
    x*=fl;
}
void wr(int x){
    if(x<0) x=-x,putchar('-');
    if(x<10) putchar(x+'0');
    if(x>9) wr(x/10),putchar(x%10+'0');
}
bool cmp(Question x,Question y){
    if(x.pos!=y.pos) return x.pos<y.pos;
    return x.r<y.r;
}
int solve(int l,int r){
    int up[N]={0},tot=0;
    for(int i=l;i<=r;++i){if(!up[a[i]]) up[a[i]]=i;tot=max(tot,i-up[a[i]]);}
    return tot;
}
void update(int x,int op){
    if(op==1){
        nxt[a[x]]=x;
        if(!lst[a[x]]) lst[a[x]]=x,vst[++cnt]=x;
        sum=max(sum,x-lst[a[x]]);
    }
    else{if(!nxt[a[x]]) nxt[a[x]]=x;sum=max(sum,nxt[a[x]]-x);}
}
void erase(int x){if(nxt[a[x]]==x) nxt[a[x]]=0;}
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    rd(n);len=(int)sqrt(n);
    for(int i=1;i<=n;++i) rd(a[i]),lsh[i]=a[i];
    rd(m);
    for(int i=1;i<=m;++i) rd(q[i].l),rd(q[i].r),q[i].id=i,q[i].pos=(q[i].l-1)/len+1;
    sort(lsh+1,lsh+n+1);
    qaq=unique(lsh+1,lsh+n+1)-lsh-1;
    for(int i=1;i<=n;++i) a[i]=lower_bound(lsh+1,lsh+qaq+1,a[i])-lsh;
    sort(q+1,q+m+1,cmp);
    for(int i=1,j=1;j<=(n-1)/len+1;++j){
        for(int k=1;k<=cnt;++k) lst[a[vst[k]]]=nxt[a[vst[k]]]=0;
        int br=min(j*len,n);l=br+1,r=br,sum=cnt=0;
        while(q[i].pos==j){
            if(q[i].r<=br){
                ans[q[i].id]=solve(q[i].l,q[i].r);++i;
                continue;
            }
            while(r<q[i].r) ++r,update(r,1);
            qwq=sum;
            while(l>q[i].l) --l,update(l,-1);
            ans[q[i].id]=sum;
            while(l<=br) erase(l),l++;
            sum=qwq;++i;
        }
    }
    for(int i=1;i<=m;++i) wr(ans[i]),puts("");
    return 0;
}