P1972 [SDOI2009]HH的项链 记录录录录

· · 个人记录

由于这是莫队板题，考虑使用莫队。

考虑到计算机处理比较的速度较快，使用 pre,nxt 搞大操作。

然后就乱杀了。。。

#define maxn 1000010
int n,m;
int a[maxn],pre[maxn],nxt[maxn],app[maxn];
int pos[maxn],blo;
struct prpr{
    int l,r,id;
    inline bool operator<(prpr x)const{
        if(pos[l]^pos[x.l])return l<x.l;
        if(pos[l]&1)return r<x.r;
        return r>x.r;
    }
}q[maxn];
int ans[maxn],res;
signed main(){
#ifndef ONLINE_JUDGE
    freopen("testdata.in","r",stdin);
#endif
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)pre[i]=app[a[i]],app[a[i]]=i;
    memset(app,0,sizeof app);
    for(int i=n;i;i--)nxt[i]=app[a[i]],app[a[i]]=i;
    for(int i=1;i<=n;i++)if(nxt[i]==0)nxt[i]=n+1;
    cin>>m;
    for(int i=1;i<=m;i++)cin>>q[i].l>>q[i].r,q[i].id=i;
    blo=n/sqrt(m);
    for(int i=1;i<=n;i++)pos[i]=(i-1)/blo+1;
    sort(q+1,q+m+1);
    int l=1,r=0;
    for(int i=1;i<=m;i++){
        while(r<q[i].r)res+=pre[++r]<l;
        while(l>q[i].l)res+=nxt[--l]>r;
        while(l<q[i].l)res-=nxt[l++]>r;
        while(r>q[i].r)res-=pre[r--]<l;
        ans[q[i].id]=res;
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
#ifndef ONLINE_JUDGE
    cerr<<endl<<(double)clock()/CLOCKS_PER_SEC;
#endif
}