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

· · 题解

讲道理这题其实不用回滚莫队(

使用普通莫队维护每种颜色的左端点和右端点，预处理出每一个位置的同颜色前驱后继，这样就可以方便地莫队转移.

然后考虑查询，有O(m\sqrt{n})次插入删除和O(m)次询问最大值，值域分块即可.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int N=6e5;
int n,m,s[N],ss[N],bl[N],blo,a[N],cur[N],tmp[N],ans[N],pre[N],nxt[N];
pair<int,int>w[N];
struct Q{int l,r,id;}q[N];
int cmp(const Q &a,const Q &b){return bl[a.l]==bl[b.l]?((bl[a.l]&1)?a.r<b.r:a.r>b.r):a.l<b.l;}
void upd(int x,int w){s[x]+=w,ss[bl[x]]+=w;}
int query()//值域分块
{
    for(int i=bl[n];i>=1;i--)
        if(ss[i])
        {
            int L=(i-1)*blo,R=min(n,i*blo);
            for(int j=R;j>L;j--)if(s[j])return j;
        }
    return 0;
}
void addr(int i)
{
    int x=a[i];
    if(!w[x].first){w[x].first=w[x].second=i;return;}
    upd(w[x].second-w[x].first,-1);
    w[x].second=i;
    upd(w[x].second-w[x].first,1);
}
void addl(int i)
{
    int x=a[i];
    if(!w[x].first){w[x].first=w[x].second=i;return;}
    upd(w[x].second-w[x].first,-1);
    w[x].first=i;
    upd(w[x].second-w[x].first,1);
}
void dell(int i)
{
    int x=a[i];
    if(w[x].first==w[x].second){w[x].first=w[x].second=0;return;}
    upd(w[x].second-w[x].first,-1);
    w[x].first=nxt[w[x].first];
    upd(w[x].second-w[x].first,1);
}
void delr(int i)
{
    int x=a[i];
    if(w[x].first==w[x].second){w[x].first=w[x].second=0;return;}
    upd(w[x].second-w[x].first,-1);
    w[x].second=pre[w[x].second];
    upd(w[x].second-w[x].first,1);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",a+i),tmp[i]=a[i];
    sort(tmp+1,tmp+n+1);for(int i=1;i<=n;i++)a[i]=lower_bound(tmp+1,tmp+n+1,a[i])-tmp;
    for(int i=1;i<=n;i++)pre[i]=cur[a[i]],cur[a[i]]=i;
    for(int i=1;i<=n;i++)cur[i]=n+1;
    for(int i=n;i>=1;i--)nxt[i]=cur[a[i]],cur[a[i]]=i;
    blo=sqrt(n);for(int i=1;i<=n;i++)bl[i]=(i-1)/blo+1;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
    sort(q+1,q+m+1,cmp);
    int l=1,r=0;
    for(int i=1;i<=m;i++)
    {
        while(r<q[i].r)addr(++r);
        while(l>q[i].l)addl(--l);
        while(r>q[i].r)delr(r--);
        while(l<q[i].l)dell(l++);
        ans[q[i].id]=query();
    }
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}

不过跑得没有回滚莫队快(