HH的项链（莫队算法模版）

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,s;
int ans[999999];
struct st{
    int l,r,h,t;
}p[999999];
int f[999999],a[999999];
int cmp(const st &a,const st &b){
    if(a.t<b.t)return 1;
    if(a.t==b.t&&a.r<b.r)return 1;
    return 0; 
}
int main()
{
    scanf("%d",&n);
    int q=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&p[i].l,&p[i].r);
        p[i].h=i;p[i].t=p[i].l/q;   
    }
    sort(p+1,p+m+1,cmp);
    s=0;
    for(int i=1;i<=m;i++)
    {
        while(p[i].l>p[i-1].l){
        f[a[p[i-1].l]]--;
        if(f[a[p[i-1].l]]==0)
        s--;
        p[i-1].l++; 
        }
        while(p[i].l<p[i-1].l){
            p[i-1].l--;
            if(f[a[p[i-1].l]]==0)
            s++;
            f[a[p[i-1].l]]++;

        }
        while(p[i].r>p[i-1].r){
            p[i-1].r++;
            if(f[a[p[i-1].r]]==0) s++;
            f[a[p[i-1].r]]++;
        }
        while(p[i].r<p[i-1].r){
            f[a[p[i-1].r]]--;
            if(f[a[p[i-1].r]]==0)
            s--;
            p[i-1].r--;
        }

        ans[p[i].h]=s;

    }

    for(int i=1;i<=m;i++)
    printf("%d
",ans[i]);
}

莫队算法就是先将左节点分块，然后排序，每个块里按右节点排序，然后一个一个区间的转换，最后找到了解，我觉得最重要的还是搜索实现方法。。。