zcmimi's blog
查看原题

点击跳转

#include<bits/stdc++.h>
const int N=200011;
int n,m,blk,nn,a[N],ans[N],mi[N],ma[N],clr[N],pre[N];
struct node{
    int v,id;
    bool operator<(node t){return v<t.v;}
}b[N];
struct que{
    int l,r,id,pl,pr;
    bool operator<(que t){return pl!=t.pl?l<t.l:r<t.r;}
}q[N];
void cmax(int&x,int y){if(y>x)x=y;}
int main(){
    scanf("%d",&n);blk=sqrt(n);
    for(int i=1;i<=n;++i)
        scanf("%d",&b[i].v),b[i].id=i;
    std::sort(b+1,b+n+1);
    for(int i=1;i<=n;++i)
        a[b[i].id]=nn+=b[i].v!=b[i-1].v;
    scanf("%d",&m);
    int l,r;
    for(int i=1;i<=m;++i)
        scanf("%d%d",&l,&r),
        q[i]=(que){l,r,i,(l-1)/blk+1,(r-1)/blk+1};
    std::sort(q+1,q+m+1);
    int tot=(n-1)/blk+1;
    for(int now=1,i=1,R=blk;now<=tot;R+=blk,++now){
        if(R>n)R=n;
        int l=R+1,r=R,mx=0,tt=0;
        for(;q[i].pl==now;++i){
            if(q[i].pr==now){
                for(int j=q[i].l;j<=q[i].r;++j)
                    if(!pre[a[j]])pre[a[j]]=j;
                    else cmax(ans[q[i].id],j-pre[a[j]]);
                for(int j=q[i].l;j<=q[i].r;++j)pre[a[j]]=0;
                continue;
            }
            while(r<q[i].r){
                ++r;
                ma[a[r]]=r;
                if(!mi[a[r]])mi[a[r]]=r,clr[tt++]=a[r];
                else cmax(mx,r-mi[a[r]]);
            }
            ans[q[i].id]=mx;
            while(l>q[i].l){
                --l;
                if(ma[a[l]])cmax(ans[q[i].id],ma[a[l]]-l);
                else ma[a[l]]=l;
            }
            for(;l<=R;++l)if(ma[a[l]]==l)ma[a[l]]=0;
        }
        while(tt--)mi[clr[tt]]=ma[clr[tt]]=0;
    }
    for(int i=1;i<=m;++i)
        printf("%d\n",ans[i]);
}
LG 5906 【模板】回滚莫队&不删除莫队
comment评论
Search
search